The "java speed sux" argument has long since been dispelled as a myth that was only ever a reality in the relatively early days. The last 2 or 3 JDKs have had performance that for most tasks is on par with native code.
There ARE still parts of the java spec that aren't too good speed-wise... anything GUI-related comes to mind immediately (although there are a number of very complex apps that perform very well, Oracel JDeveloper is the best example I can think of).
The speed issue is no longer the case because generally because the JIT compilers have become so good at optimizing that they can gain efficiencies that a native program can't, enough to overcome the inherent slowness of a virtual machine architecture.
Look at it this way... when you write a C program and compile it, it's in it's final form, that's the native code that's going to execute. But at runtime your program has more information about what it's doing, the data it's fed maybe, the condition of the underlying hardware, etc. Too bad! Your program still runs as written.
Contrast this with Java, where the JVM has A LOT of information during runtime and can actually perform optimizations on-the-fly to your code (within limits of course). This is a very powerful feature, and one of the main reasons Java is now, speed-wise, comperable to native code for most tasks (and there are examples out there of studies that show it being FASTER in some cases).
Now, jumping to the question of running full Java on a PDA... I would certainly agree that Java uses much more memory than a native app, sometimes frightingly so! For that reason alone it's not really well-suited to limited resource devices, and it's the reason J2ME was created... They took out most of the parts that would cause memory and speed penalties on such devices, and rewrote others to make it more applicable. Even still, I have a J2ME-capable cell phone, and while the apps run acceptably, including a couple of decent games, it's not on par with native apps.
So, don't diss Java!
You can say it's not great on a PocketPC, and I'd agree, but in general the speed argument just doesn't hold water any more.