How about introducing in the game the old fashion games like solitaire, backgammon, battleship, etc but with a GW2 Tyrian style twist?
There are a lot of NPC in major cities that could offer some coins for the challenge
The matches can be done versus the NPC or some other players, randomly chosen from all servers. A sort of old fashion traditional PvP
If there are no players available for the challenge, then the NPC takes the role for that. Whenever a player is selecting the challenge it will be matched up with others.
Here is a list of classic games that could be adapted for GW2
http://en.wikipedia.org/wiki/List_of_board_games