I actually started a game recently as Kazakh as I thought it'd be a nice, challenging game (my previous runs had been with Pommerania and Mutapa). It's most certainly not an ideal nation for trying to learn the game. Heck, none of the Hordes are: they work very differently than other nations, and all will eventually require Westernization in order to avoid a game over screen (by the 1500s, my Kazakh was in danger of getting overrun by Austria if we didn't escape tribalism and Westernize... which, thankfully, we did).
A stronger European nation is honestly your best bet to learn things. Castille and England are the popular "starter" nations, as both start off as the big fish in their respective ponds and in prime position to carve your own destiny. If you want to be in the HRE, Austria and Bohemia are also both solid choices. Heck, might as well at Sweden to that list.
But just starting out, you should stay in Western Europe... the only non-Western tech nations that might enter the argument are the bigger Russian states, as you can still get a decent ways into the game with Eastern tech. But Westernizing is a pain in most cases, and is one of the most frustrating processes in the game. Sadly, it's virtually absolutely necessary in order to succeed as a non-European nation. There's plenty of guides on it/using non-Western nations, which are helpful whenever you're ready to try it out. Not counting Eastern Europe (cause that's barely westernizing), I'd say the best place for your first non-European game would be someplace in India or Yemen/Oman. It'll be a while before Europeans can reach you, and by the time they can you'll be ready to start the westernization process.
Oh, and I'd say EUIII is most certainly "strong enough" without mods. Heck, the only PDox title I've played where I felt mods were necessary was Rome. Mods with EUIII are purely up to the individual player's preferences, I'd say.