This seems tough, but I'll consider it as my second option.
Thats not really that tough, and it also is something that applies to "everyday" game programming in general, so you better get used to that.The concept of having a plain list of objects, but still organizing those objects in some other datastruct for different uses should appeal naturally. Just imagine a scene graph, or space partitioning data structure like an octree or quadtree. One would never store objects directly and only in such a structure - unless you feel cool with traversing the whole tree for simple tasks as Update()-ing those objects.
Just think about it as one place where the objects are stored and truley belong. Then there are theoretically unlimited other containers that might store those objects, specially laid out for a certain processing task - be it frustum culling, collision, ... . Just as you need it.