Sir Walter Raleigh will appear at some point in the 1570s (or perhaps early 1580s), and then stick around for 30 years or so, giving you plenty of time to discover the world. Until then, the single best way of exploring places like America or the Far East is to sink some Spanish or Portuguese ships and steal their charts.
IMHO, the value of America is a bit overrated. In purely exonomic terms, it pays much more to go to India and the Far East (stick a colony on the west African coast, one around the Cape of Good Hope, and 1 on Reunion and you can get to India pretty much without attrition problems even if you don't have an admiral or explorer). I'm currently raking in over a thousand cash per annum from control of 2 CoTs in India and Asia alone (it's 1651).