Yes, J2ME requires you to install a JVM which weighs in at 585K on my PDA. For a single midlet to use this, it is quite large, but if you have half a dozen or more, I'm sure that could mitigate the size issue. This is one of the prices you pay for
Java's cross-platform-ness.
I've recently started developing Palm apps with C and GCC's PRC tools. While these are bound to create smaller prc files, it is somewhat complex just to set up a simple "do nothing" app, let alone one that accomplishes something useful.