What notchristopher said, such games are sandbox games/nonlinear games or open ended games. To some extent they are all RPGs in one sense or another.
Can I also suggest if we are going into PC land you take a trip to
http://www.moddb.com/ and similar sites as the mods often far exceed the scope of the original game and turn "normal" games into such games.
For straight up walking around
Elder scrolls (Oblivion is an entry in the series)
Mount&Blade
GTA
Saints Row
Stalker, 2 games in this series.
You also have roguelikes
Far Cry 2 (I am bored with listing shooting games as there are a fair few open ended type games available now).
The Witcher (not so open ended but well worth a play, get the enhanced version if you can)
If you are willing to expand the scope many of the space sims are this sort of thing.
