Naval attrition has been debated here at length. Many feel that it's too high, though I think most are comfortable with the current settings once they examine how it affects the rest of the game. The design choice here is a balancing act: As you've pointed out, exploration can be too difficult if attrition is set too high. On the other hand, if it is set too low, colonization will proceed too quickly and around-the-world invasion armadas would become too common. Given all the factors involved, and all that is impacted, I think the current settings work well. They encourage the use of ports to extend naval operations and that's as it should be.
Exploration is still possible once you get used to it. I typically am able to uncover far more territories, far more quickly, than I have colonists to exploit them. Following the approach I outlined above, I haven't lost an explorer in a long time.
A couple of specific observations:
1. Add a ship to the 3 you start with. I usually take away 2 of the warships and add 3 transports. I don't know what country you're playing, but you should be able to scrounge up an extra ship with little difficulty.
2. You can get to the New World and back in one piece. You won't be able to explore the entire Carribean or Atlantic Coast in one trip, but you should be able to uncover at least a couple potential port colonies.
3. Uncovering two or three provinces in your first voyage is reasonably 'realistic' if you consider that discovery of a province entails not only sailing past it, but also opening up the interior. The results are sufficiently historical.
4. In his first voyage, Columbus landed at a small island northeast of Cuba, then explored a small piece of the northeast corner of Cuba and then part of the northern coast of Hispaniola, before returning home. (In fact, he explored so little of Cuba that he didn't even realize it was an island.) That translates to only 2 or at most 3 provinces in EU terms. For a map of Columbus' discoveries on his various voyages, check out
http://encarta.msn.com/find/MediaMax.asp?pg=3&ti=04279000&idx=461514477.
5. If you look at the map, you'll see that Columbus actually needed four separate voyages and 12 years to explore what amounts to maybe 10 provinces in EU terms. If anything, exporation is too easy in EU.