My personal favorite is the
suckerfish menu. The JavaScript is minimal which may help spiders.
I think though anytime you add JavaScript of any kind you're putting up a barrier to getting spidered. Search engines seem to have gotten much better when it comes to reading JavaScript, but I'm not sure they're quite there yet.
My own solution when I want to use a dynamic menu is to provide an alternate source of text link only navigation usually as a menu in the footer.