Don't feel bad about VNV Nation, I count myself as a fan :p
edit: My sister has been really into VNV Nation and Apoptygma Berzerk for awhile, so I picked up "Of Faith, Power, and Glory" for $5 at my local record store and I was hooked. Still haven't checked out Apoptygma Berzerk.
I tentatively recommend Clan of Xymox to a VNV Nation fan; among my friends, they either love them or hate them. The band is weird in that it has 3 distinct eras which sound significantly different. Early era COX (Self-Titled, Medusa) is very "Sisters of Mercy"ish, and "mid-era" is when they were basically a dance band (Twist of Shadows [which is an EXCELLENT dance album], Phoenix), and then "late-era," where they really settled into the VNV Nation type of groove (Farewell, Breaking Point, In Love We Trust). And then there's the albums that don't fit, like "Hidden Faces" and "Creatures," both of which I would recommend to ANYONE (particularly "Hidden Faces").
2nd edit:
I agreed with the Amazon review of "Creatures" that said: "This is not Clan of Xymox's comeback album (that would be 1997's "Hidden Faces"). This is Clan of Xymox's "We are SERIOUS about coming back" album."
3rd edit:
I don't count "Headclouds." That album was turds on a stick.