How about an option to make a blind challenge where the opponents deployment screen is blank, like deployment in expert difficulty missions, taking away some of the defenders advantage. Or perhaps only getting information about the number of each class of ship, but not the actual formation. (This would tone down spam fleets).
You know, what will be really nice with this is a random mode, where a challenges from the person you choose is randomly selected. This way, you can never be sure what the next challenge will be.
Unless it randomly selects the person, all this does is make a high likelihood of adding one almost-certain loss before any victories.
Well what if a challenge consisted of 10 or so deployments so you would get a random deployment each time you made an attempt? You would never be sure what you will face - well at least after 10 tries you might figure it out.