How do I best measure the query performance?
I like to use the SQLQueryStress free tool when comparing a before and after scenario. With SQLQueryStress you can execute each stored procedure as many times as you like, and get the total average stats for all executions.

For example, you could execute each stored procedure 100 times, and then use the stats to back up your improvements. "Over 100 executions, my improvements save a total of 30 seconds and the stored proc does 1500 less reads per execution." I think you get the idea.

If there are parameters in the stored proc, it's always a good idea to double check that your improvements work with many different sets of parameters. SQLQueryStress does some cool stuff with letting you substitute parameters in your query to get a better overall picture of how the stored proc might be performing.

SQLQueryStress documentation: http://www.datamanipulation.net/sqlquerystress/documentation/documentation.asp