There is a new game on the market called Solitaire Challenge
This is the only game were you can play Solitaire in real time against other players.
Both players start wit the same cards and the winner is the first one to finish the game.
A leaderboard is available based on a ELO rating system. Players are matched also based on the ELO rating.
Android Market Website link