Hehe thanks. The key is not how many men you can recruit, because whatever you do they will be no match for the French, Castilian, or Aragonese armies. You have to establish friendly relations with them; the best thing is to grant them military access (the AI never cancels it). Also, make strong alliances where you can; I was lucky to get an alliance offer from Austria. I must say though that in this game, because of the start date, I only had to deal with Castille and France, seeing as Aragon is a Castilian vassal, so it's one less country that can screw you over.
If you really want to expand in Europe, Ireland is a good target; small, weak, and isolated, the Irish minors are an easy prey if you have strong allies. I was too late and the English conquered it all first, but you might get luckier.
Otherwise, just do what you would do with any small nation: trade. Navarra starts strongly oriented towards Free Trade, so it's a little bit easier. Mint a little bit (Navarra is strongly centralized, so you get a 0.04 inflation reduction), take loans if you must, and colonise; it's the only way you will be able to expand (my inflation is about 5 right now). Also, it will make it harder if attacked to get annexed. And in the worst case scenario, you can relocate your capital there.
A piece of advice: trade efficiency and competitieness is not really something to worry about given you're Free Trade, so the only trading National Idea I would take is "Merchant Adventures"; with cheaper merchants (about 1 ducat! each), it's a lot easier to get started.
P.S: Luck helped me in this game though; I almost got conquered twice.