In order from highest priority to lowest:

Fix CSS usage
Administrative interface
Duplicate post prevention
Don't show lrpd for Anon users
Factor posting functionality (quote buttons disappearing, etc)
Search
User-selectable caching controls for dynamic pages
Stats

Of course, once you get down here, everything is more-or-less the same.

Mark forum category read
Collapse forum categories
Parent thread listing above content
Page titles
NNTP Gateway
Mail-on-response
Killfiles
Show New Forums Only
Alternative nesting spacing on showContent
Move authentication to Login Manager
Pagination on forum displays
Single SQL for forum list

I think the CSS/HTML should be addressed first because I think that would be easiest to change now rather than later. And an Admin Interface would let other people Do What Needs To Be Done that doesn't involve coding.

Duplicate Post Prevention and No LRPD to Anon users are important parts of the casual user experience. They shouldn't be forgotten about or we will eventually get newbies complaining about them. The Quote button interface etc is similar, but I think we can spend some time to explore options with that. Rather than a line of buttons for quoting, a dropdown box to select the style and a single button "Quote" would look better. It may also let you add a default quoting style to a user's preference sheet, and even arrange for pre-quoted replies by default.

Search is important, but right now we can afford to wait a little while because there's not that much content to be searched right now. But don't wait too long.

Wade.