First, if you have a large number of tiles of one particular size that are in a regular grid (for example, the tilemap itself), keep that separate if you've already got an efficient way to handle that. If you're mixing all these map tiles into what are probably a much smaller number of odd-sized sprites/tiles, then your problem is really that you're paying the high cost of your search-a-single-list approach for probably several times as many graphics as you need to. You only want to pay that cost for the items that you don't have a better solution for.

A quad-tree or similar spacial-partitioning system is the general approach and if you have a fairly even mix of tile sizes and such it might be the best fit. But it comes at some complexity -- for example, if a movable image like an NPC or enemy moves between partitions, you have to update those lists. Its not especially hard, but other solutions are simpler if you don't need the full generality of that solution, and if the number of odd-sized/non-gridded objects is relatively low.

Sorting your list in various ways can help too, so that you don't have to iterate the entire thing every frame. For example, you could sort the entire list based on distance to the viewport, and decide on some larger-than-the-viewport distance that includes the entities you need to consider every frame. Now, you iterate through only those "near" objects every frame, and periodically you resort the whole list -- maybe once per second. You don't even need to do a full sort, you just need to partition the list into 'near' and 'far' parts -- in C++ that would be std::partition or std::stable_partition, but I'm not sure what the best C# equivalent would be.

Some other implementation details to be aware of are:

• You don't want to literally move the list contents around if they're expensive to copy, you'd probably want to sort a list of references. In C# this is probably already taken care of, just be sure you know about how structs/classes differ. In C++ this would be an issue you'd have to deal with yourself, either by sorting through a list of references, or possibly by making the objects cheap to move.
• You probably don't care about the *actual* distance for this sorting, so save yourself the cost of a square-root per object by just squaring the threshhold (once) instead. You'll get the same order/partition out regardless.