I’m a guy who’s always looking around, exploring all the little side-hallways, saying “What happens if you press that button?”, collecting all the alternate whatchamajiggers, and so on. Any advice on a console or computer game I might like?
Elder Scrolls: Morrowing/Oblivion might be games you’d like.
They have huge game worlds with many things to interact with.
If I may suggest the crazy far end of this: one of the Tony Hawk Pro Skater games (any that start with the phrase “Tony Hawk’s”).
I’m a great fan of games that give you a detailed environment and set you loose in it to explore, too, and that is what I really like about these games. You get a large environment to discover (particularly in the later games) and skateboard tricks are the means to exploring it. And you can get most of them fairly cheap so you don’t lose a lot by getting one and deciding that I’m just crazy. 
Get a Dreamcast and play Shenmue. There’s no other game like it.
I woudl agree with this. Even though, I personally, can’t stand the game, it’d be right up the OP’s alley.
I also think any of the <B>Zelda</B> games would fit, due to the vast amount of hidden items.
The Gothic series are very good RPGs with quite the backstory, though also a heapload of sidequests and derails. It all feels quite alive, too, especially in contrast to recent Oblivion.
That said, you might want to hold out on Gothic 3 for a while yet, though it’s been recently released. It’s quite buggy - nigh unplayable, some say - but wait a while and let the mod community have a go at it. The first two games are still pure class, though the graphics haven’t dated very well.
Wow, most games involve exploring and puzzle solving. But it sounds like you’d enjoy a game with a lot of free exploring, as opposed to a linear point to point game.
The Grand Theft Auto series of games have hours and hours of free exploring you can do while ignoring the main game story line.
On the Gamecube, Zelda Windwaker has a huge map to freely explore.
Metroid Prime and Metroid Prime Echoes also have large, explorable maps but the game play can sometimes be a little tougher if you’re not an experienced gamer.
Resident Evil and Silent hill games require a fair bit of exploring, plus you get the added advantage of never knowing when you’re going to scream and wet your pants.
What about Shenmue 2 on the XBox. I think that was rather like Shenmue. 
Did they reissue the first one (Shenmue) for the XBox? If not, is there any damage to the story’s continuity by starting with 2?
Shenmue 2 comes with a DVD that contains the story for Shenmue 1. I’ve played both but I don’t think there’s really a problem with starting at the second one.
Fallout 2 has sooo much hidden stuff.
My friend is a total expert on the game and finds something new everytime he plays (IIRC it’s about eight times he’s played it through)
The first one is better.
Shenmue 2 has atrocious voice acting, which is enough to make me lose interest in it since a huge portion of the game is talking to people. But the major issue for me is a deeper one. In Shenmue, everyone in the town knows your character, in most cases all the way back from childhood, since you play the first half of the game in your hometown. Walking through Dobuita and Sakuragaoka is like visiting a familiar neighborhood and seeing your friends, once you get into the game.
The Hong Kong setting of Shenmue 2 is much more alien. Nobody knows you, and everyone is a stranger who is trying to trick you. In addition, the environments are not as nice to look at - jarring reds and yellows with slick advertising everywhere. Shenmue (1) has a much more aesthetically pleasing atmosphere.
Hmm…many excellent suggestions. I’ve beaten GTA, but it’s still fun to throw in once in a while. Ditto Silent Hill and RE. Fallout I enjoyed muchly also.
Zelda sounds good, but I have only a Playstation 2. Gothic also sounds interesting.
I know you asked for computer/console games, but I just got done playing Seven Noble Kinsmen, a Shakespeare-based Flash game from the BBC. There’s a review of it here from Casual Gameplay. It’s really diverting, especially if you like mysteries.
Another vote for Zelda Windwaker on the Gamecube. I abandoned the plot for long sections to explore.
Two rarer purely exploratory games are Everblue and Everblue 2 for the PS2, diving games from Arika. The game action is almost pure exploration, with occassional quests and a loose story, and you can dive anywhere on the map to find items. Everblue only came out on PAL and Japanese format, but Everblue 2 is available in all regions and has a better range of minigames.
Sky Odyssey is also exploration, although the flight controls can be awkward.
On the PC, I found that Sacred allows you to abandon the plot to roam freely and find a lot of hidden miniquests.
As an avid adventure gamer, it’s sad for me to see that in 14 responses, there is not one adventure game mentioned. Most adventure games are nothing but exploring, pressing whatjamajiggers and collecting inventory. Have adventure games fallen this low into obscurity?
Assuming you really want to do the things you asked and not just mindlessly kill things and blow shit up, here are some adventure games that I enjoyed:
Riven
Legacy of Time
Amerzone
Grim Fandango
Longest Journey
Blackstone Chronicles
Myst 3 (Exile)
The Beast Within
Syberia 1 & 2
Riddle of the Sphinx
Dreamfall
Alida
Starship Titanic
.
Oh god, that game. I still shudder thinking about it. Trying to come up with the phrase they exactly needed to get things done… text based adventure games did it better 15 years ago.
Sure was pretty, though.
Any adventure game will do you, most likely. Anything by Lucas Arts (Grim Fandango was mentioned, or you could try Day of the Tentacle or Full Throttle or The Dig. Google “ScummVM”) Those are kind of linear, but still have hidden stuff for exploring.
Oh man, I forgot about Riven. I have a Mac version and a PS2 version and haven’t yet made it all the way through either. Now that’s a game for exploring and lever pulling and button pushing. It’s not really a free roaming map, but definitely lots of exploring.
Here is an entire blog devoted to a subset of the type of games you mention. I recommend Aquaria (though it’s short) and The Roomz. (TAKE NOTES, AND WRITE DOWN THE SOLUTION WORDS AND THE WORD THAT MAY APPEAR AS THE DOOR OPENS TO THE NEXT ROOM!) The last game there is EVIL. I haven’t checked in on it recently, Mr. Clawbane said he fullly expected that soon the devolper would require you to have a microphone hooked up so he could hear your wailing and gnashing of teeth. It’s HARD, but addictive!!! (Yes, you will have to do websearches, and figure out things like the Playfair cipher and Braille.) If you are really, really stuck, check out the forums at Gamershood for the enormous thread devoted to the game.
I just saw on the blog, (haven’t checked it in a bit…) that MOTAS has new levels as well, in case you didn’t know.