Wow, I remember Exile. I originally got it from a 150-in-1 games CD, too! Possibly the same one?
Fun to note, the company is actually STILL ALIVE! They make a few more games, and still sell full remakes. I thought they still had full versions of the older ones, too... Mostly, I was really happy a company from my youth was still around, and I love to see a small-time company actually making it.
Also, agreed, Ultima Underworld was great. So was the whole series, for that matter. A very similar game that's probably on my top 10 games of all time is System Shock. The sequel is just as good, and perhaps even better if you prefer more actual RPG elements. There's even another spiritual sequel, Bioshock, set for release this month (I can't wait)! If you like SS2, Deus Ex could be up your alley as well.
For people who dig melee combat, there's always Witchaven, or if you like newer, prettier, NOT-CAPSTONE games, there's Rune: Viking Warlord. Run actually reminds me of another great old gem (that I also got from that 150-in-1 CD! Surprising the actually GOOD stuff you can find on those considering how cheap they are, and how MOST of it is crap. At least, the older stuff, back when shareware and small companies thrived in the computer business. The newer ones probably suck) is Champions of Zulula. <!-- m --><a class="postlink" href="http://www.christianboutin.com/osparchive/">http://www.christianboutin.com/osparchive/</a><!-- m --> has that and a few other neat games.
Geez, I did it again. Once you get me started it's hard to stop me. Hell, let's just turn this into an "awesome old and similar games" thread.