Is that, to perform a push, the BlackBerry user MUST be on a BlackBerry Enterprise Server? If I haven't subscribed to use the BlackBerry Enterprise Server, can I still push data to my phone?

A BES is not required.
As long as you have a BlackBerry Data Plan provisioned on your account, you'll get Push email delivery with BIS (BlackBerry Internet Service).
You can integrate POP, IMAP, GMail, AOL, Hotmail, Yahoo Mail, etc... using BIS.

For immediate push email, your email provider has to support the IMAP IDLE command. It's a case-by-case basis. Without IMAP IDLE you are subject to the "every 15 minutes" schedule for delivery to your handheld.

To get read/unread to sync both ways and deleted/not deleted to sync both ways you need BES.

Not necessarily.
For example, Yahoo is real-time push and doesn't use IMAP at all.
Yahoo also offers two-way reconciliation of deletes and read/unread marks.

Hmmm. I always assumed they were IMAP since their last update, but we all know how dangerous assumptions can be. Yahoo was one of the first of the major free email providers to make their services as compatible with BlackBerrys as possible.

Unless the OP is asking about MDS data push, in which case the only non-BES option at the moment (as far as I know) is the Web Signal API.

All BB email is push. However, keep in mind that with BIS it's push between BIS and your BB. BIS can't magically transform an email account into push so you may be stuck with 15 minute polling intervals with certain email accounts (see above).