Your idea about removing the "and" is a future feature (removing "stopwords"). It will be a toggle though, because I prefer to have a proper phrase in the url. If you remove stopwords like a, and, the, then the category and product names might not make sense. I'm doing this mostly for user experience
A few things that I might do to clean up the URL a bit, is:
1. Remove "default" variables (cat isn't needed, and page=1 is a default, so the page variable would not display unless it was a value other than 1)
2. Eventually I'll move to storing SEO'd URLs in the database, that might improve the overall speed some, and it should allow us to get rid of the _p1234 bit.
Thanks for the feedback