Q: Fewer photos in Photo Stream compared to iPhone

The photos you are seeing in My Photo Stream are not necessarily the same on all devices.

iCloud stores only the photos that have beeb uploaded during the last month, and at most 1000 photos.  When you enable My Photo Stream on a device, it can only download what is currently in iCloud.  Your other devices may still have stored older photos that are no longer in iCloud.

Photo Stream on my Mac only synched the photos that had been uploaded to iCloud in the last month (even though there are actually 1000 photos on the Photo Stream on my iPhone?)

Yes, if you start My Photo Stream new, it can only download from iCloud, what is still kept on the iCloud servers. see:

Get help using My Photo Stream - Apple Support

I see different photos in the Recently Added album or My Photo Stream album on each of my devices.

Your device will keep up to 1000 photos, even if they're older than 30 days. Photos older than 30 days are removed from the iCloud server, so your devices might not have the same photos, depending on when you enabled My Photo Stream. Due to storage limitations, your Apple TV might display only your most recent photos.

Use these steps if you want to have the most current photos from My Photo Stream on each of your devices and delete the older photos:

1. If there are any photos in the Recently Added album (or the My Photo Stream album in iOS 7) that you want to keep, save them to your device, then back up your photos and other data using iCloud or iTunes.
2. Turn My Photo Stream off in Settings > iCloud > Photos.
3. Confirm that you want to Delete Photos.
4. Turn My Photo Stream back on. iCloud will automatically push your stored photos to your device.
5. Repeat these steps for each device.

You're welcome, Ann!