Kinneas: the problem I see with your ideas is this:
Sure, it would be great if players can impact the storyline by being the first to do something, BUT I have a stong feeling that the players that get the recognition you mention will be players that have lots of time to play. That's good for them of course, but the problem I see is with the casual player: someone who doesn't have much time, but really likes to play STO anyway. If it's the most dedicated players scoop up all the rewards, I think the casual players may well feel left out, and eventually leave the game, because they feel they can't contribute.
So in short:

Or do you want it so 'leethxor69' on day one has just as much chance to make a difference as someone who has played for a year and has become specialized in exploring?

No, but if the noob would work for a long time (say a year or more) at building his character, he should eventually be able to do the same things as the more senior player.

In my opinion, replayability in MMOs is too key to have being the 'first' to do something be a main goal.  You leave out the majority of your player based consistently, which sounds, honestly, like a really bad idea.

Alternately, using the progressive generation we've spoken of, everyone can be the first to explore somewhere, and we can all go around collecting firsts.  Yes, players who've been on longer can be the first in more places, but space is a big giant place with a lot of stuff going on around in it.  Flying the furthest out may give you some kind of record, but it doesn't make you the first to discover the hundreds of thousands of star systems you've passed by.  In a big vacuum, finding 'lanes' is simply not a big deal, nor should it be.

As for limits, I think it should be a skill check.  Once you're good enough to be far out there in some of the worst areas, then go for it.  If you're not good enough, you'll get outsmarted by the computer repeatedly, or cower as your more powerful Captain handles all the light work and you just earn piddling 'watching' XP.

To directly address the topic: I think Exploring should be rewarding, and offer surprises, challenges and spectacular visuals.  I think that will make it fun for many.  I think integrating it with missions of various types will make exploration fun for all.  Charting space is okay, but a lot of what I've seen of Star Trek involves surveying and exploring planets, from the surface if need be.

I would like new kids to be able to make a difference if they're smart and skillful.  Sometimes the Ensign saves the day, especially if they're Wesley Crusher.  I would like people who only play a short time, who are smart and skillful to be able to advance, perhaps not in as diverse ways as those who plug a lot of time in the game, but increase in rank and general power for completing a certain ratio of mission success over a certain time frame.