I really like LuxChomp and Gyrados. I haven't playtested against Lostgar at all, but I'd assume that Gyrados might be hurt a bit more because they can LZ your Magikarps. I have quite a bit of experience with LuxChomp, and Gyrados can definitely hold its own.
Of course, in half of the games I've played against Gyarados, both my Lucario GL and Azelf were prized. That's my luck.