iTunes: m4a, has your name and email address encoded
Amazon: mp3, has Amazon's unique song id in the ID3 comments
And in terms of the cloud:
iTunes: $25/yr for iTunes Match, which is completely optional
Amazon: Free storage for songs you purchase from Amazon + 5gb extra
The important issue is to keep your music backed up, since both Amazon and iTunes offer limited options if your harddrive fails.
Anyway, to address your point, Dropbox or a manual file transfer would be your best bet for multi-device support.