They probably just seem like they get colder because of the higher conductivity of the aluminum. The downside is that they don't stay cold nearly as long as a plastic bottle. The condensation that forms on the outside of a cold can expends a lot of energy into the liquid.
It’s also surprisingly easy and cheap to make your own sparkling water. If you get a counter top unit, people make CO2 adapters for them that let you use standard 5/20 lb cylinders rather than the way overpriced ones the original vendor has. A standard 20lbs cylinder will last 22x as long as the cylinder the units come with, and don’t cost much more to exchange. A welding supply shop typically has food grade CO2 for roughly $1-3/lb as they also supply all the nearby restaurants.
If you want flavors without sugar, bitters used for cocktails make for a easy way to flavor the water you just carbonated.
Plastics recycling is a much more delicate process, requiring all sorts of washing steps and finely controlled relatively low temperatures.
It's not that recycling aluminum is easier than other materials, it's that making aluminum from raw bauxite is like the above process times ten. The chemicals are even more dangerous, the process management (environmental protection, regulatory compliance, etc) more expensive, and it requires even more energy. As a result, between 1/3 to 2/3 of all aluminum sold in the US comes from recycled materials because of economic reasons.