Castille and the Ottomans are probably the easiest overall to learn with, but I ended up going with a bit of a dark horse choice. Admittedly I had already played EU3 a lot so I knew the basics, but I still needed to learn all the new stuff like Monarch Points and Idea Groups, limits on diplomacy, etc. So this may or may not be a good idea for a total beginner. But I went with one of my EU3 faves - Malaysia. Er, Malaya. My reasoning:
1) They're effectively the Portugal/Netherlands of the Pacific, so you can learn naval warfare, land battles, trade, and colonization all at the same time.
2) The nations that can form Malaya are all the only Sunnis in a land of Buddhists, Confucians, Shinto, and Hindus, so you can learn how to either holy war or play the diplomacy game to keep the non-Muslims off your back.
3) The nations that can form Malaya all hate each other at the start so you can learn about Rivaly without too many super-powers wanting your land (see 4), and you can learn warfare, vassalization, and annexing in your quest to unify and form Malaya, and the main people that you'll get the larger Aggressive Expansion penalties with are going to be the ones you're going to war with anyways, so it's easy to keep them in truces when you're not at war with them, so even if they form coalitions it won't help much.
4) The closest thing to a super-power that actually cares about Malaya at the start is Ayyuthaya, and they usually have they own issues to deal with on the mainland early on. By the time they do turn they're attention to you, you should already have either formed Malaya, or at least have most of the land controlled or vassalized. And Ayyuthaya is no match for a unified Malaya. By the time the Japanese turn their attention to you you'll be on equal footing power-wise, and could probably easily blockade them and crush their fleet if necessary, rendering them helpless. In my experience (admittedly I didn't go into late game), Ming rarely cares about you for a looooong time.
5) You start off in the Chinese tech group, and since Malaya is a prime colonizer you can put yourself in a position to be near enough to the West to westernization without risking them attacking your heartland.
6) About 50 - 70% of the provinces you'll be focused on colonizing all count as part of Asia, so you get full tax. And spices and chinaware are valuable trade goods even for Eastern powers, and with your access to Australia and Africa you can get a decent amount of gold provinces if you want them.
Of course, the drawbacks are that many Europeans have missions to take your land, the Chinese tech group is pretty bad, and being the only local Muslim power means that you're going to be without allies or Royal Marriages outside of vassals for several decades, until you can extend your territory west far enough to lessen the distance penalties with the main Muslim powers. At least in the case of the Europeans, if you can Westernize early enough and take Naval/Quality ideas you should be able to field a navy large enough to stop them from being able to do anything to you outside of Africa.
edit: Just realized I forget to talk about the countries themselves. Makassar is the smallest, and frankly worst choice. It's the best choice for a first vassal though, even though it doesn't count towards the territory needed to form Malaya. Malacca has the trade node, but it's the second smallest, and adjacent to Ayyuttayah and Aceh. If your navies bigger you can block the straits to stop Aceh in their tracks, but you're still in a risky position. Aceh has the most land and easy access to Malacca if your navy can beat theirs. Not sure how they are on Manpower, but they have a decent base tax. Brunei though has the best base tax (I think) and the only way to reach it is by water. Crush everyone's navy and you're safe, and even if they do land they'll take landing penalties. You'll have to have transports to fight back of course. But I think it's the best choice of the four.