I find different civs and even just different games to be wildly different in terms of potential for an interesting late game. I've really taken a liking to Indonesia lately because I think they are the most consistent in providing one since you can delay your growth as long as you like without really losing your opportunity to burst outward whenever is most opportune or interesting. Cree are fun too because you get to watch all your allies, so even if nothing fun is happening to your Civ, you're still likely to have something interesting to pay attention to. The French are great as well because you get to watch everyone (indirectly with the rumor system), and the only limit to how much of an advantage you can make from this is your game knowledge and attention to detail, I find it fun to just sit there and watch the reports and try to predict how future events will play out. Poke a bit here or there and see If I can manipulate those events with as little effort as possible. Watching those notifications is annoying when you're not used to it or aren't deriving much from them, but the more you watch the more they are like the code in the matrix, the abstract representation falling away to reveal the underlying narrative of the game, so it becomes more like a story.
I guess I think you sorta have to be able to create your own fun, and the best way to do that is by being somewhat reactionary to the AI and the map, and treating the game more like a simulation than a competition. The victory conditions just aren't very interesting, and if anything they're just a distraction from having fun I think. If they're all you're focused on, then yes, at any given point, sometimes even on the first turn, they're just a forgone conclusion.
Another way to mix things up is to pick an AI to sort of sponsor, and try to make them win with as heavy or light a touch as you like. Pick one who's very far behind if you want a real challenge. Or just pick little goals to keep yourself interested, like creating the best trade city possible and seeing how many of the AI trader's you can attract... there's no limit of ways you can challenge yourself -like picking your own much more interesting victory conditions. Having naval access is very important though, at least for me. Tedium is definitely a problem, and I think it's why the game defaults to the small map size. It's better now that smaller civs are more viable, but using a navy to project power instead of land units really lifts a huge burden of complexity from the late game without necessarily limiting what you can do.
I love playing France and watching the messages scroll. Keeps it interesting between turns, too.
Think I agree with everything you said except trying to get someone else to win - but only cause I don't have vc's enabled. So I go for 'balance.'