And I don't mean strategy games like Galactic Civilizations II and the like -those let you control an entire, well civilization. But what about you (OK, your character) personally taking a ship out into the unknown?
Let's stop and consider the most likely candidates.
The X-Series of games
I really liked X-3 Reunion, the only part I actually played. But even here, you have an in-game universe that is already known to most people in it -it's just unknown to the player. You can do almost everything here, even building entire fleets or industrial empires, if you want to.
But there is not much to actually discover -no unknown alien species, no unknown civilizations, no undiscovered parts of space. If you take a ship and just fly off somewhere to the border of the known universe, it just ends there. Normally you would expect to find something new after you left your "officially" mapped world behind -not here. No secrets here.
So, either follow the story or do something else. You can be a mercenary, for example. Many ships to blow up for you. Exploration? The Unknown? Far to scary. Better to just take on one of the few "allowed" things you can do.
Space Force: Rogue Universe and Evochron Mercenary
Essentially from the same mold as the X-Series, just more modern and less good. Evochron has the most freedom out of the two, but it is still a rather sterile sort of freedom: Be a mercenary, a racing pilot, a trader, everything is possible! But flying an exploration vessel into complete new, scary, unknown parts of the universe just to explore? Why, that is of course to boring! And impossible, since the one-man project of EM apparently didn't thought of it.
Space Force? Well, if you want to blow up ships in space it's not so bad, I think.
Astonishingly, even if you essentially wage war among the stars, the Homeworld-Series of RTS games comes at least near the ideal: Your fleet even finds remnants of old, long-lost civilizations. The problem is the same as with strategy games in space, though: You control not a single character, nor a small group of characters travelling the universe, you control an entire fleet -in the first Homeworld, your entire civilization, since you are dragging the last survivors of your people around after your homeworld got burned.
The Mass Effect-Series
Exploration is at least possible in parts one and two. I don't know much about part three, though. And besides, the focus of Mass Effect is the story. In a real exploration game, the story has to take a back-seat, because you would feel pretty silly otherwise: "So, the evil space monsters are eating our worlds? I don't have time now, there are still two solar systems I haven't been to yet. Maybe I can help next week?"
Since I included Homeworld, I felt guilty by not including Star Ruler: Star Ruler is by far one of the best strategy games I found in a long time, but I still have to disqualify it on the same technicality: It is good and full of exploration (AI-Races are more or less generated automatically, you can only influence minor things, like their general behaviour or how many you start with, the rest is completely unknown to you as player, until you actually meet them.), full of remnants and other neat stuff to find, but it still is only the next best thing: You can follow your self-designed exploration vessels around, but you can't actually be the captain of one. If you want that feeling of a new species exploring space for the first time, Star Ruler is for you.
But as I said, If you want to feel less detached and explore the unknown for yourself, tough luck.
Essentially a newer version of the age-old Elite. Strangely, with its possibility to just buy some kind of super-hyper-mega-jump drive and then jumping to a complete new galaxy (and then again -several times), it has more "real" exploration feeling (at least for me), then X-3 and Evochron combined.
A bit of an odd duck. On one hand, you actually have the possibility of outfitting your ship for research and exploration, you can even follow a related profession and just go on your merry, sciencey way -on the other hand, it's a MMORPG. So in a way, everywhere you go, thousands of people were already there.
And suddenly, your feet stop itching.
By that I mean the classics I know: Star Control II and the Starflight-Series. Both had what I just keep missing from modern games: You had your ship, your crew -and knew next to nothing about your surrounding universe. Sure, there was an overarching storyline, but you had to actually fly out and meet new aliens, find neat artefacts and all that. You could trade, shoot at people and stuff -but you also had to continually explore new places.
I'm sure you could have just followed the plot as close as possible and keep exploration to a minimum, but that's the point: You could explore. And there were places were your ship was the first human presence, like, ever.
A few titles from the early age of video games and Eve Online, a MMORPG? Seriously? That's all?
Wow. Maybe I should just learn to program my own game then, I guess?
And on a side note: First, isn't it weird we like to see stuff like Star Trek, where there is a ship exploring around, doing exciting stuff, but when we want to play computer/video games, we apparently only want to trade things/make things/make things go "boom"? Is there some kind of allergy against a sense of wonder in the gaming community I'm not aware of?
Second, why only humans? I mean, there are niche titles like Space Empires V that lets you conjure up the wildest things your imagination can handle for your soon to be empire-building race (Seriously, want a species that looks like catfish, breaths hydrogen and likes opera? Take a picture from a real catfish as avatar, write a few snazzy sentences, take the necessary picks in the beginning, done.) but if it comes down to flying around in your own ship, the availability of races that aren't looking astonishingly humanoid for that kind of thing is even worse then the availability of new games like Star Control II. By which I mean, less then one. Zero. Nada. Nothing.
Well, as long as I'm silently suffering under my Fernweh, I'll ease the pain with Starflight TLC.