Paladin is not bad in Arena. I went 6/3 with one earlier. Only 'bomb' drops I managed were two Guardian of Kings - 7 Mana for a 5/6 with +6 Health to you. Other than, loaded up on 'pumpers' (Defend of Argus as a rare, two Raid Leaders, and one Stormwind Champion) and went to town with weenies.
Rogue is by and far the best. I had a 'mediocre' pool earlier (Not much to combo with, but did score two Assassin's Blades and FOUR Leper Gnomes) and went 8/3 (Would have had 9/2, but was disconnected once - Which counts as a loss).