Some sort of sidekick or otherwise just nasty character. All the companions in F:NV are either neutral or friendly. I'd like it if there was atleast one companion who would only join you once your karma was low enough.
EDIT:
Actually to expand on that I have a suggestion for the addition of two companions:
1) A mischevous dirty cowboy type of character. His quest(s) would be some sort of robbery. Stuff like that. A rotten apple but not exactly evil.
2) An ex-slaver turned legion supporter. This guy would be a real nasty apple. He had been slaving across the mojave but was being chased down by NCR rangers. That's why he joined the legion.