Would it be possible (or desirable) to create a handicap system of sorts?
At first I thought banning rare cards for one player (like in the AI challenges), but that may be a bit extreme, so I thought of other variables you could adjust:
Card draw odds
Amount of cards in hand
+x to card costs
I know at least some of those are probably unimplementable but I thought I'd list them anyway.
Most likely, these wouldn't see THAT much use in PvP, but against the AI player, they might be fun: a bit like creating your own challenge! Or for comparing your decks ("This new deck can beat my best deck if I give it 'X' advantage.), or just for playing against the AI. That poor AI must be so tired of losing, I think it's time we gave him a chance!