I just purchased a new Clip last night, and today when I hooked it up for the first time I see that instead of 4GB there is only 3.65GB on it. 

I haven’t loaded anything on it yet—in fact, I deleted the few songs that were included.

Is this normal for a new player, or do I need to return it?

It’s normal–operational files take up some space.

That’s normal. For all flash/hard disk storage, there’s a roughly 7% difference between the manufacturer’s claimed capacity and what will actually be measured by the device it’s installed in. This is because manufacturers use the decimal definition of “gigabyte”, while electronics see things in binary terms. To the manufacturers, a gigabyte is 1,000,000,000 bytes (10^9), while computers etc. define it as 1,073,741,824  bytes (2^30). So 4,000,000,000 / 1,073,741,824 = 3.7252902984619140625, or ~3.72 GB. The remaining “missing” space is used by the system files etc.

This isn’t a new issue, by any means. Look on the box for any flash card or hard drive and you’ll see small print explicity stating the “1GB=1 billion bytes” thing.