How about handling sorting on the stuff displaying the results -- grids, reports, etc. rather than on SQL?
EDIT:
To clarify things since this answer got down-voted earlier, I'll elaborate a bit...
You stated you knew about client-side sorting but wanted to steer clear of it. That's your call, of course.
What I want to point out, though, is that by doing it on the client-side, you're able to pull data ONCE and then work with it however you want -- versus doing multiple trips back and forth to the server each time the sort gets changed.
Your SQL Server isn't getting taxed right now and that's awesome. It shouldn't be. But just because it isn't overloaded yet doesn't mean that it'll stay like that forever.
If you're using any of the newer ASP.NET stuff for displaying on the web, a lot of that stuff is already baked right in.
Is it worth adding so much code to each stored procedure just to handle sorting? Again, your call.
I'm not the one who will ultimately be in charge of supporting it. But give some thought to what will be involved as columns are added/removed within the various datasets used by the stored procedures (requiring modifications to the CASE statements) or when suddenly instead of sorting by two columns, the user decides they need three -- requiring you to now update every one of your stored procedures that uses this method.
For me, it's worth it to get a working client-side solution and apply it to the handful of user-facing displays of data and be done with it. If a new column is added, it's already handled. If the user wants to sort by multiple columns, they can sort by two or twenty of them.