If serving with a particular captain meant during the era in which they were captain, I would have to choose Archer. The simple reason for this is that they were the first ones to get "out there" and do some serious exploring of the unknown, for the first time. That, to me, would've been memorable. Picard would be a close second, for similar reasons.
If I was looking to get into a fight, then I'd have chosen Sisko, then Jellico, and then Kirk.