Java: Well, there is the JIT( Just-In-Time ) Compiler, which compile java code to native binaries. This helps speed tremendously, and is the only way to go in games with java ( to some extent. Small games like Sonic games can easily use Java VM without any speed problems. 3D accelerated games though, will be very very slow in the VM, and the JIT is REQUIRED in order to get performance)
EDIT: Sidenote: Just because there is a native compiler doesnt mean Java is a good choice for games. Java is very very high level, and very unsuited for performance needing applications/games. On the other hand, C and C++, are both very low level, and offers lots of flexibility, and great communication with hardware. And they are the languages which there is most information on, so theres always a good tutorial suited for you. Dont take any shortcuts, C or C++ is the way to go. There is a C compiler for almost every platform out there, theres even C compilers made for the kind of chip that is inside your mp3 player!