I think you're on the right track.
Your first two examples are pretty good ones; things like warmth and beauty are hard to quantify, and so the word relative can apply.
Greatness in music is also hard to quantify, but the greatest in history is a superlative, so I don't think “It's all relative” works as well there. Typically, the phrase is uttered as a way to say, “There's no sense arguing about this, we'll just have to accept that we're looking at this differently, and neither of us is right or wrong.” Indeed, in the end, the two engaged in the music debate may also have to “agree to disagree,” but I still don't think “It's all relative” is a good way to summarize that disagreement. Perhaps if the argument was:
He thinks Green Day is a great band, I say they're just alright.
then “It's all relative” would apply more aptly.
As for the last one, I don't think “It's all relative” applies to just any difference of opinion, there should be some sort of quantitative difference in the argument. So if you set it up like this:
She thinks the budget will result in significant savings; he thinks it'll only be a drop in the bucket.
then “It's all relative” would do better job of describing the disagreement. In your original, there's nothing relative about the argument, they are arguing about whether or not the budget will “save millions.” Sure, that's quantitative, too, but it's only when that argument shifts to a question like, “Do those millions represent a ‘lot’ of money?” would “It's all relative” come back into play.