If possible, one thing that may help is to do the sorting in the application.

Creating an index on the view sounds like it will probably be your best bet, but the restrictions on doing that are rather long. (I've only tried once, I don't remember why it hadn't worked) Check 'Indexed Views' in BOL for the list.

Keep in mind, adding an index on the view means that the server will have to maintain the index whenever you do anything with the underlying data, so test it to see if it unacceptably slows down inserts, deletes or updates.