This depends a lot on the type of animations you're doing. For example:
1) If you're not scrolling the screen, then it's likely that not ALL of your screen is changing each frame. In PacMan, for example, only Pac and the Ghosts and maybe a pill or two change each frame - large portions of the screen (though WHICH large portions varies) remain the same.
Therefore, you can do quite a bit with 'dirty rectangles' and 'setClip', updating only those parts of the screen which absolutely need it.
2) Using Java's built-in 'sleep' or 'wait' is never going to be as good as the 'hires Timer hack' on the 'Shared Code' section of these boards, which in turn is never going to be as good as a native hi-res timer. Being able to reliably space your frames 'exactly' the same amount of time apart increases the smoothness of your animation a great deal.
3) The quality of your graphics is unlikely to affect their speed unless you're rendering them each frame, in which case...
4) ...cache as many things as you can within temporary Images, ready to be quickly 'drawImage'd to the screen. Expire your caches when images in them aren't used (to save memory)
5) Use double buffering, or triple buffering if your frame rendering time can get quite high...
6) ...and use VolatileImages (hardware accelerated) to reduce frame rendering time
Just my two cents