What "natural" does even mean? That's a vague philosophical argument. And even then, all versioning systems deal with versions, not changes. Changes are relative to different versions. This is true even for SVN. Changes are always relative, it doesn't make sense to track them as the based unit conceptually or even for performance. Different versions implies change, not the other way around.
> If you run `git show $SHA`, git will show you a set of changes. But that's a lie; that's not what git stores.
Each new version will bring a change. This is not a lie. Sure it could show the entire corresponding tree by flooding your console, or it could be more practical and merely show the diff from the previous parent(s). This is the kind of thing that people who do not bother to take the time (about one hour) are stuck with. Don't worry, it's not that hard.
> Many users expect (quite reasonably, before they've been bitten) that if you start from scratch and apply those changes in order, what you end up with will be the same as your current tree. Nope.
The author, the date and other data about the commit do matter. If you rebase your commits, which is effectively applying those changes in order, then very very likely you will not have the same snapshots of the filesystem. And even if the filesystem remain the same, the data about the commit will be changed. It seems that your expectations of what a CVS "truly stores" is naive and based on a lack of experience.