My favorite deck in Shandalar is:

4 Lightning Bolt
1 Disintegrate
1 Balance
1 Disenchant
1 DT
1 Regrowth
1 Time Walk
1 Ancestral Recall
1 Timetwister
1 Ring of Maruf
1 Aladdin  (!)'
1 Swords to Plowshares
1 COP red
1 Ivory Tower
1 Black Vise

Black Lotus
Sol Ring
5 Moxes (all 5 colors)
4 Strip Mine
3 Volc Island
4 Plateau
2 Taiga
2 Badlands

The point of the deck is to bolt the enemy to death, while stalling his development with strips, swords, etc.  The Regrowth ALWAYS recurs the Timetwister, unless you can get a card to win immediately.   Disintegrate is a great finisher, and is helpful at removing creatures.  COP red is necessary, since a burn opponent is the one deck the AI plays that can deal LOTS of damage faster than the rest of this deck can handle it.  

The Ring of Maruf is there only because all games in Shandalar are played for ante - if one of my key combo cards is ante'ed, the Ring gets it back.  Aladdin is my way of dealing with opponents with multiple artifacts - he's the Mox Monkey of Shandalar.

This deck has NO difficulty dealing with the final boss.  And I always play in hardest mode.  

A tip for those journeying in Shandalar and trying to assemble a deck:  use the save/reload trick right before walking into one of the random shrines that appear in the landscape.  You will often find yourself opposing a tough enemy that antes some very nice stuff:  power 9, etc.  If you lose to him, you lose nothing.  Also, sometimes you get a "Nomad Bazaar" which lets you purchase most of the cards the computer knows about - so you can get those 4 bolts quickly.

I recommend the "Wizard mode" when starting out.  Yes, it's harder and opponents have more life, but the "drops" are also much better.