Most everything by Paradox Interactive does a good job. The main ones being Victoria 2 ( More economy focused ) and Hearts of Iron 3 ( More combat focused ).
Just be prepared: These games make Civ 5 look like a simple kids game. Absolutely everything about Vic2 and HoI3 has massive amounts of variables, and takes a lot of work. On the flip side though, conquering the world is a major accomplish and feels great. Instead of being the normal conclusion of a couple hour game, its usually a rare conclusion after several weeks of time and effort.
Some first start tips: Don't pick a Great Power, or probably even a secondary power. It'll be a bit of an information overload, and your country is much more likely to fall apart on you. I like to go with Japan in Vic2, and I forgot who in HoI3. In vic2 Japan starts uncivilized, but is on the brink of civilization. Many other countries have either a lot longer road to civilization, or have too much going on for a beginner. Once you have learned the basics, you can then go back and try other countries for different challenges.