Hmm..
open-ended naval strategy...
I hear
War In the Pacific is a huge one controlling the whole Pacific theater. I've not tried it since my attention span is lacking. Hell, I still haven't finished up the precursor Uncommon Valor. Time intensive.
http://www.matrixgames.com/games/screens.asp?gid=294
As for other open-ended strategy games, they seem few and far between. For an easy-going yet enjoyable empire building series I can recommend
Spartan (Ancient Greece) and it's predecessor
Chariots of War (Really Ancients). Neither too extremely intricate but it'll keep you thinking on what you should do next running the kingdom. Kinda relaxing and a nice change after the hard-core ones but they still have diplomacy, trade, and all the usual trappings of running your own kingdom. Bargain priced with a no-hassle digital download option at Matrix.
http://www.matrixgames.com/games/game.asp?gid=312
http://www.matrixgames.com/games/game.asp?gid=341