The first one I tried was France and it just seemed too confusing, "slow" and perplexing.
Then I followed someone's advise and played USA. Also a bit perplexing to adapt to how the events figure into it; but since I know 19th century US history and US geography much better than I know French or European, I was able to get going playing US. I played through many restarts as US up to about 1880.
Then I tried Prussia. Prussia is "the best." It is small enough that it is manageable early game (though learning all those provinces, is a real challenge, hey! that's why we play these games right! And heck! Now I know where Kattowitz, Erfurt and Dortmund are relative to Hannover!

). Prussia is also in a "high-underdog" group at the outset=they have a lot of money, they have a reasonably strong military they have a pretty well developed industry, and they have tremendous capacity to grow (and indeed dominate) in all these areas. However, they are in a somewhat risky situation, sandwiched between France, Russia and Austria. Events and how the player anticipates and responds to them can exacerbate or leverage these risks. The idea of playing a total underdog I think is not very appealing when you first learn a game, but perhaps neither is playing the top dog.
Despite many (many) restarts as Prussia (first in Vanilla, and now most recent two or three are in VIP) I have yet to finish a play through without any cheating (which is my goal). I would call that replayability!