New to Arduino: Should I learn C, C++ or both (C & C++)?
The basic syntax of C and C++ is very similar, to the point that C code can typically be compiled directly as C++. You'll also find C standard functions (such as printf and malloc) can be used from C++ programs.

The major difference in the core language is that C++ has a lot of extra stuff such as classes and templates. Conventionally, C++ also has a huge standard library which doesn't work on C. However, that's not usually available (nor really appropriate) for Arduino programming, so you don't need to worry too much about it unless you migrate to e.g. desktop programming.

Basically, it's probably sensible to learn C first, because the same knowledge works in C++. You can then move on to the C++-specific stuff, such as classes.

As a side note, the Gnu Compiler Collection (GCC) actually covers both C and C++. It's what the Arduino IDE at Atmel Studio use under-the-hood for all their compilation. It's even possible to work directly with GCC but still upload programs to Arduino via USB.

It's also worth noting that programs compiled within the Arduino IDE aren't necessarily going to run any slower than programs compiled some other way (whether C or C++). The main difference is whether or not you use the Arduino functions. Since they are general purpose, they're not necessarily doing things the most optimal way. You could get more efficiency in theory by manipulating the microcontroller's special registers directly, which is you can do from within the Arduino IDE as well. It's usually very tricky for a beginner though, so it's probably not something you want to attempt until you're more comfortable with C/C++.