I'm not sure that I totally understand your question: are you building a site and wondering if you should make it beautiful with AJAX or readable for search engines with a clear category structure? Or do you already have a site with AJAX and now you've taken the time to come up with a category page structure, but you're hesitating to implement it?
If it's the first, I don't think that you should think that your choices are 1) be usable/beautiful, or 2) be search-engine friendly. There are a lot of ways to make an HTML site beautiful. You can use new enhancements in HTML5, or build a standard HTML site and then use JavaScript to make elements more interactive.
If it's the second, I'd go with Thomas's suggestion and test your AJAX site to see how readable it is for Google. AJAX isn't readable by Google, but the underlying HTML is, so there may be enough HTML links that Google can still get around your site.
Once you've tested how readable your site is, then you have to decide if this interface is worth pages being missed or ranked lower by Google. My guess is that you can probably keep your site the way it is primarily, but you'll have to make some tweaks. It's hard to give specifics without knowing specifics, though.
Good luck!