• We have updated our Community Code of Conduct. Please read through the new rules for the forum that are an integral part of Paradox Interactive’s User Agreement.
Many recommend Brazil here too, but I disagree. My suggestion is Sweden.
 
You might think Beowulf is biased judging from his location, but I would also agree. :)

Brazil isn't a bad first country, but things will move a little slowly, especially in terms of research. Sweden is much better for that, and will allow you to get your feet wet in terms of industrial development and such.
 
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!
 
I started with belgium and i'd say it's one of the best. You start with just two starting states to manage (and a little bit of luxembourg) and a capatalist in each will industrialise them quite well (in revolutions). The war you start with will almost always end in a few months by event regardless of how bad you are losing. After you get your economy up and running you are free to expand your colonial empire, attack bankrupt minors and build your own colonies (as soon as you have the machine gun tech). It's relativly easy to elevate yourself to number 8 and become a great power. It's also perfectly viable to invade the netherlands for territory or ally with a great power against france (french are one of your national cultures). You can get tons of manpower from your colonies (tunis and egypt are especially good).

It's only my very first game (aside from the tutorial) and i'm playing on normal/normal. I've conquered 2 french provinces and all of zeeland in the netherlands. I own 80% of borneo, alot of pacific islands, malaya, egypt, tunis, the majority of west africa, all portuguese colonies (they kept going to war with me) and some of their mainland, i have a population of 32 million and i'm no.7 in the world, it's the 1890's. I've survived a war with germany and france (thanks to my allies) I'm sure alot of people can do better, but it doesn't sound too bad for a first game. My bad boy is in the 30's which leads to constant wars with protugal spaina and holland though, even logn time firend france attacked me :(