Some other good games I tried out recently and really enjoyed were Nitro Games titles, published by Paradox IIRC.
Conquest of the Americas and East India Company Complete. Both available via Gamersgate for pretty cheap. Be sure to get East India Company Complete.
Sort of like Sid Meier's Pirates! but with more of a trade-network development slant. Lack of land combat is a flaw in both, but the basic economics/strategic balance, the flavor, and particular the tactical naval combat are the best I've seen for Age of Sail strategy genre.
I've bought many Paradox titles now, and I'm happy with all of them, even the ones I didn't really get into (e.g., Arsenal of Democracy). Sometimes their games have some imbalance initially, or some bugs, but they are renowned for smoothing out those bugs, and I see this pattern as a reflection of the sheer complexity and detail in the games they make. It is inevitable that a game as complex as the EU series will still have bugs even after beta-testing. Since Paradox does a great job of refining, accessorizing, updating, expanding on their titles, I don't see this as a flaw in their business, just something you should be aware of. Like any of these games, they eventually get repetitive and boring, but with alternative settings, mods, playing different positions, or just taking a break from them, you can come back and be much refreshed. I'd say their games have been just about as replayable to me as Civ4 BTS was, though perhaps not quite as replayable as Civ3 Conquests. Arsenal of Democracy will eventually get all balanced and patched up, and I'll go back and give it a whirl; if I'm in the mood for that flavor, I've no doubt I'll "get my money's worth" at that time. This is the thing about Paradox titles as compared to Civ (esp. it seems since Civ4): they do not try to be all things to all players. EU focuses on a particular set of dimensions of history, during a particular historical period (as opposed to conceiving itself as a "simulation of all of cultural history" or something conceivably broad) 1400 to 1820(?). Victoria same thing, 1820 to 1930. Historical processes and themes that are represented in great detail in Victoria are largely absent from EU and vice versa. This is I think a more valid and reasonable approach to a strategy game that seeks to simulate history.
What is "TBS?"
ADDIT: for another good glimpse of how 1UPT hex-based strategic can work quite well (and even achieve a need for combined arms integration) check out Slitherine's "Commander Europe at War" published by Matrix IIRC. There is a user-made expansion to it that is really fantastic. Think it is available as a DL on Slitherine's site. If anybody has trouble figuring out what that means, just let me know and I'll suss it out for you . . .