Shall I take C#/C++ or Visual Basic for AVR Programming?

well since you do embly then learning any other of the said languages will be easy for you, given your situation I'd say go for C/C++!