One trick for graceful degredation is to not have to override the styles, like this:
<noscript>
  <style type="text/css">#menu span:hover ul {display: block;}</style>
</noscript>
Of have a linked stylesheet the same way with all of these for-non-JS-user styles.
Or, do it via a class you apply to #menu that you can remove so the rules no longer match, like this:
#menu span ul {display: none;}
#menu.noJS span:hover ul {display: block;}
And in your script just remove that class:
$("#menu").removeClass("noJS");
As a side note, you can slim down your code using .hover() and .slideToggle() like this:
$('#menu span').hover(function(){
  $(this).find('ul').slideToggle('fast');
});