As you said, Frodo and Magic64 will be too slow for a bare A500. A64 will work at a reasonable rate on a standard A500, though, if you configure it properly. However, even optimal settings won't much help the speed of C64 games that stretched the original machine (i.e. games with lots of animated sprites on screen at once like Armalyte or Turrican 2; games with funky graphics routines like Starglider 2, Elite, Battle Command, or any of the Freescape 3D games such as Total Eclipse).
If there's a faster C64 emulator for a standard A500 than A64, I doubt that it will run anywhere near as much stuff.
Anyway, let us know the results of your "tests" of A64 on your A500.