My favorite part about Ultima 7 is the huge world to explore, finding unique areas/items/easter eggs in every nook and cranny of the gameworld.

Anybody aware of any other games similar in this way?

The Magic Candle
Wasteland
Might&Magic games
Betrayal at Krondor
Fallout games
Morrowind

I've heard the Divinity series is similar. Many people compared Original Sin to U7

Divine Divinity is what some people say is the game Ultima VIII should have been. It is an excellent world game, but it is more akin to Ultima VIII than VII. I have heard the same about Original Sin and I imagine it is probably so since Larian has been moving in that direction.
Another good world game (although extremely hard at the beginning) is Gothic II. Now that Nordic has returned to GOG, that one's available again. It also has a good, large world and interactivity with the world. You can cook, farm, and do many of the things you can do in Ultima VII. You may even be able to bake bread, although I haven't tried that yet.

Maybe Madman when it gets released.

GOG turned it down (boo) but its going to be released on desura soon, from what i read

http://www.machgryphon.com/index.html

To play Devil's Advocate here, I can see why GOG turned it down. It looks like freeware, or at least some cheap Shareware shlock; the best I can say about it is that it'd be perfectly commercially viable in the early 90's, but today? Now, I'm not saying its' bad; gameplay is what matters first and foremost, so I can't properly judge Madman unless I play it. But when it comes to selling it, I can see why many would turn it down, including GOG.

Looks a bit like the Spiderweb games. I'd give it a shot.

Surely you mean you cant judge it at all unless graphics mean that much. There are plenty of games here that look no better or worse.
Likewise, I cant say whether its a good game or not, but it appears to match the OPs needs.

The relative pros and cons of Gogs stance were mentioned in this thread (from post 51 onwards)

http://www.gog.com/forum/general/madman_an_ultimalike_rpg_coming_soon/page1

and if any are interested in it, here is the wishlist page

http://www.gog.com/wishlist/games/madman

The first Deus Ex game had many secrets and areas to explore that are completely optional, for example one of my favorite areas to explore where the alleys and waterways of Hong Kong. There is even an exploration bonus you can get for discovering these areas.(which come in the form of skill points)

Actually, Dr. Dungeon started this game in the 1990s as a follow up to Ultizurk. I remember reading about it as far back as 1998. If anything, I hope it brings back Ultizurk 3 and 4, and maybe some new Ultizurk games.

As ZapMcRaygunn says, the Gothic saga is highly recommended (Gothic II specially). I also like the freedom of movement The Elder Scrolls games give.
I have not gotten the same exploration experience with any other games than this three sagas, Ultima included.
If you are very brave and, not mind the ASCII style, you could also try Dwarf Fortress Adventure Mode.

Spiderweb games tend to be very open and a lot of fun to explore. I've only played the early Exile/Avernum games so far, but the design philosophy seems to have remained pretty constant over the years.

Baldur's Gate 1 (semi open world)

Every Elder Scrolls game

Fallout 3 + Fallout New Vegas

Betrayal at Krondor + Betrayal in Antara

Drakensang 1-2 (semi open world)

Neverwinter Nights 1-2 (semi open world)

Might and Magic 1-9

Realms of Arkania

Pillars of Eternity (semi open)

Arcanum

Two Worlds 1-2

The Witcher games are rather open. Semi open for the first two and very open for the third.

Wasteland 2 is open'ish too.

Ultimately, I find that in spirit the Divinity series is closet to what Ultima was trying to do. A fantasy story that nonetheless doesn't take itself too seriously that has little bits of flavor scattered everywhere. Someone mentioned the Magic Candle series above, are those games really that good??

The first one is better than any of the Ultima games, except maybe Ultima V.