A melee build with either a fighting style similar to (to provide the same sort of challenge) or dramatically different from (if you're a 2-h greatsword wielder, he's got a spiked chain) is a good place to start. The trick is to make someone whose style perhaps accomplishes the same that yours does, but in a different manner. He shouldn't be inferior to you, and he shouldn't have abilities that work you after one round (you after all need to function as his rival too).

Also if your rival's a spiked chain fighter for example, you would have been upping your strength even more or gotten some ranks in balance to better succeed on opposed trip checks. If you have an instagib move he should have a very high chance of avoiding that, victory in a one-on-one challenge should come down to tertiary strategies and tactics.