Rogue Deck:
Backstabx2
Deadly Poisonx2
Argent Squirex2
Evisceratex2
Shivx2
Amani Berserkerx2
Bloodmage Thalnos
Bloodsail Raider
Defias Ringleader
Novice Engineer
Perdition's Bladex2
Fan of Knives
Big Game Hunter
Shattered Sun Clericx2
SI:Agentx2
Ancient Magex2
Defender of Argusx2
Gagetzen Auctioneer
Sylvanas
Got the idea for the deck in my first rogue arena run, when I got 3 backstabs and an ancient mage. The idea is to use your numerous cost efficient removal tools to keep board control. With board control you can give your minions spell power with the ancient mage and throw out devastating backstabs/shivs/eviscerates/fan of knives to both maintain the board and/or burn your opponent down.
Mage deck:
Arcane Misslesx2
Mirror Image
Argent Squirex2
Mana Wyrmx2
Frostboltx2
Amani Beserkerx2
Bloodmage Thalnos
Novice Engineer
Sorc's Appx2
Cone of Coldx2
Acolyte of Pain
SSCx2
Fireballx2
Dark Iron Dwarf
DoAx2
Sylvanas
Argent Commanderx2
Pyroblast
Sorry, this is a netdeck! Pretty much a straight copy from specialistsc, but I think he doesn't use thalnos and instead uses two engineers, so you can do that for a poor man's version. Idea is to get in some early damage and let pyroblast do the rest. Specialistsc is like a top 20 player in the us in ranking and this deck has won several tournaments.
Paladin deck:
Light's Justicex2
Blessing of Mightx2
Eye for an Eye
Noble Sacrifice
Redemptionx2
Repentancex2
Secretkeeperx2
Equality
Argent Protectorx2
Bloodsail Raiderx2
Dire Wolf Alpha
Knife Juggler
Mana Addict
Novice Engineerx2
Divine Favorx2
Aldor Peacekeeperx2
Harvest Golemx2
Truesilver Championx2
I thought I was going to have to face a lot more mages so I wanted to make a deck specifically to counter them. I literally just thought this up this morning and I never played it before the tournament. I had to play it once, which was against Chysamere's warlock and that was a poor choice. It didn't help I got a horrible draw, but also as a heavy aggro warlock he had few cards in hand making my divine favors garbage. I tried build an aggro pally deck in the past and it was just too slow, then it dawned on me, rogue has such good early game because of their hero power, so light's justice must be op right? So I added repentances so I could easily kill any minion they play. Then I did a number of things to keep my minions alive, I threw in the redemptions, a noble sac, you have argent protectors, a number of the minions have 3 hp so they don't outright die to blizzard and harvest golem has his deathrattle. With all the secrets Secretkeepers seem like a no brainer, also mage plays their own secrets so this card can get out of hand. An equality to again kill with the light's justice if needed and aldor peacekeepers to make sure you don't take too much damage while doing it. Mana curve goes 12/10/6/2 so you're almost guaranteed value divine favors. No idea if it works though, I did get to play against themaster's giant deck once with it after the tournament and didn't quite all go as planned, but it did win regardless, so maybe! This deck probably loses pretty hard to most other things though, it would likely strictly be a tournament mage sniper deck. Oh also one eye for an eye to both try and get the mage to kill themself and keep them guessing.