Sachys made a funny! :P

Back in the cellar Arseface - unless you want the hose again!?!

umm let's see.

Yume Nikki
OFF
Space Funeral
Eversion

though I can't really say that I've played all that much of most of those

There is also the

- Borderlands games
Better than fecal bombardment from outer space.

A really phuqed up dyslexic could work something out with Arx Fatalis, but other than that I got nuthin' :)

Another World - you are literally taken to an alien world. Even though it's rather linear the exploration is great. You will find a lot of epic places, fight with locals and avoid other wild life forms. A true classic!

The original Dune - it's a unique mix of strategy and adventure. You can freely explore the Dune, finding Fremen's Sietches, smugglers' outpost and enemy fortresses. After some time you can even ride a sandworm and even later you can try to change the Dune into a green paradise.

Geneforge series - a world of Shapers mysterious people who can shape living organism to do their bidding. Furthermore you'll find genes-alerting devices. Trust me, it's very unique and not ye-old-generic-fantasy-world.

Myth series - perhaps it may not be so cool nowadays since zombies and undeads are overused now but back in 90s those RTT games were very fresh and inspiring. Exploring the world and facing new undeads was really cool! Especially because you don't get to play as a hero who smashes everything around him. You are outnumbered so it's not your task to kill all undeads (that's impossible) but you should fulfill the mission's objective (like escorting someone) and then watch how the story progresses.

Sanitarium - in this adventure game you explore different levels and each of them is a creation of a madman's mind. Highly recommended!

If you liked Morrowind you will probably love The Shivering Isles add-on for Oblivion too.

Also, Psychonauts seconded, it won't get much more stranger than that.

I can also recommend the Wizardry series. The end of 6 introduced Sci-Fi elements and 7 and 8 expanded upon them. If <span class="bold">6 and 7</span> are too old (in terms of presentation or gameplay) for you you can go straight to <span class="bold">8</span> if you want, though as always it's a lot more satisfying at least knowing the earlier parts' stories.

And for something completely different have a look at Bad Mojo (Redux).

If your definition of "strange" included Steampunk worlds then of course you should try <span class="bold">Arcanum</span> too.

And [Licurg]Buy <span class="bold">Sacrifice</span>[/Licurg].

King of Dragon Pass : A barbarian tribe tries to settle a land populated with strange nonhumans, where myths and legend are real, and where the mortal can enter the spirit realm and walk along the gods. I love the fact that everything has a mythic feel. The world? Flat. The stars? Holes in the dome that separate the inner world from the fire gods realm. The sun? A god's chariot crossing the sky and then falling into hell. The local river? The body of a water godling you can talk to if you make the proper sacrifices. Sickness? An evil spirit infestation, that can be exorcised.
The world of Glorantha is simply awesome, and that game is a great first contact with it :)

Banner Saga : Dead gods, an immobile sun, and groups of human and giants trying to survive the world's end.

The Longest Journey series (especially Dreamfall) : several worlds linked together by dreams. Even the "near future" world has an eery feeling to it, with its strange machines and the way it interacts with the more magical realms.

The Neverhood
https://www.youtube.com/watch?v=Q-79BZ5-zCA

This! One of the most crazy and entertaining environments I have played in. So much fun!

As others already said, Outcast is also a great choice. I felt like playing my own Stargate adventure.

Cargo! The Quest for Gravity

Giants: Citizen Kabuto
Waking Mars
Botanicula

maybe Aquaria, Insanely Twisted Shadow Planet, Limbo, Bastion and Transistor (although the latter three are quite limited with regard to exploration), and Neverwinter Nights with the right module suggestions

if you like the look of NaissanceE, you could also check out Kairo