I am trying to decide what is the best solution for "most recently used" collection. Intuitively, it's neither LIFO nor FIFO. as far as "removing" items it's FIFO; but as far as "retrieving" it's LIFO. So, both queue and stack have some limitations.
Or I am overthinking this whole thing and should just stick to Arrays or Lists?
I would suggest a LinkedList collection. The LinkedList holds references to the first and last node in the list (effectively letting you travel in LRU/MRU order). It also has
Remove methods so you can remove the value and move it when a value from the list is used. MSDN