Leaded gas won't melt your converter, the lead just coats the catalyst and makes it unable to perform it's job. The thing that will melt a catalyst is excessively rich mixtures that cause the cat to run extremely hot as it burns off the excess fuel.
Unless you're running some major compression or timing, excess octane is just wasted. If you record some history from the ECM and find the knock sensing system is retarding the spark, then higher octane will improve power and performance. Otherwise, it's just money blowing out the tailpipe. It is also a good idea when using racing fuels and lubricants to verify all the necessary detergent ingredients are included. Racing engines that get torn down every 500 miles don't need that stuff, but your street engine surely does.
As for the original question, yes I have seen a difference in performance many times when using a different brand of fuel. There can be large differences in the amount of alcohol used by various refineries, which will affect driveability. There is also the freshness factor, since some stations sell very little premium the stuff tends to sit in those tanks for a really long time. And then you have the "accidental" dumping of the incorrect grade into the premium tanks. Midgrade or regular sold at the premium price will tend to ping a little more than the good stuff.
Jerry