Definetly go for the grey. As much as I love a great pair of black shoes, I think the grey patent is much more interesting than the black and I can imagine you could have a lot of fun with them! Not just with black pants but with jeans too.
I can also see these shoes with tights and a skirt or dress. Since I'm short I'd go with tights the same color as the shoes for an elongating effect, but I think, if I recall correctly, you have proportionately long legs, so you could probably pull off something in a funky color like purple or pink....
I've seen that look lately in mags (often with peep toe mary janes or t-straps) and it's grown on me.