Trying to be serious here; I think that when you hit the right tone of burgundy you can have a very classy look. Don't go for brown shoes; they are or too close (definite mismatch) or too far away (another mismatch) from the color of your outfit.
Black only if all options fail; there is a pretty big chance that black shoes under a burgundy suit make you look like a porn star or worse, a would-be porn-star.
Safest choice; middle to dark grey or even better, anthracite. Grey sounds boring but when you wear a suit that atracts attention the last thing you want is a pair of shoes that do that too.
I must to the barber's, monsieur, for methinks I am marvellous hairy about the face