I'm of a mind of Gimli and Legolas from the Lord of the Rings, particularly the films. They certainly were antagonistic towards each other to start with, but over time and shared adventures, they became very solid friends and even treated combats as something of a game, which tracking their respective body counts.
Granted, it's going to take some give on the part of both characters to get over that initial prejudice, but as long as the players are willing to put in the effort, it could lead to some really great role-playing on their parts.