That you have embedded your queries into StoredProcedures is a very good step because SQL Server will make some execution plans to run them.
Your queries seem to be at their most optimized state (read here
in-vs-join-vs-exists/[
^]) so try to work on application side. If you are working with millions of record do not try to show all of them to user try to group them in alphabetic manner or some other grouping criteria that you know better.
Adding a where clause and confining the result set should improve your application performance.
Also consider using some UI controls that support lazy loading.
Hope It Helps.