You haven't provided nearly enough detail about your problem to really get at the potential problems. Based on what I've read you may have one or more of the following problems (among others which may not be listed here):
- Bad algorithm.
- Poor memory access patterns.
- Bad memory allocation and usage causing excess garbage collection pressure.
Updating only tiles within your "update radius" should be very fast unless your radius is so large, that it contains the entire map. Even then, you'd have to have a colossal map to have it take enough time to notice a really long pause (~1 second or more). How are you determining which tiles are in your "update radius"?
Maintaining homogeneous lists of each tile type could be advantageous, but you pay for it with memory. Suppose you put each type of tile in its own list and each list element points directly to the actual tile in your grid. This gives you the advantage of not having to search the entire grid for all elements of a certain type. But you're paying for this advantage in speed (by not having to search) by spending memory to have all that information already computed. I would say it's a worthy trade as long as your game requires you to perform many operations/queries on only subsets of your data, where your subsets typically match your tile types. If you have operations that require iterating over the entire 2D grid anyways, then this may not be worth doing, since at each tile you visit, you could perform the operation right then and there.
Creating new tiles entirely for the update is probably a bad idea. C# is garbage collected. If you create tons of new tiles every frame and remove references to the old tiles, you could be creating enormous pressure on the garbage collector. You should avoid orphaning data at all costs and just mutate existing memory if you want to avoid garbage collection hiccups.
Your description of "update" is woefully vague, but I suspect your update is performing something pathologically expensive or your overall algorithm for iteration is just far too excessive for what you want to accomplish. Even for large 2D grids, you shouldn't have much of a problem updating the entire grid if you've carefully designed your algorithms and data structures.