This is the first time that I'm using a VPS instead of shared hosting for hosting my domain names.

I've figured out how to get web sites running with Nginx, but getting email to work is MUCH more difficult. The solutions I've tried so far are:
1. Postfix/Dovecot/MySQL + a web interface: I was able to get Postfix/Dovecot/MySQL to work without error messages, but I wasn't able to get SquirrelMail working, and I was unable to access my email through my email client.
2. Citadel: I was attracted to this solution, because it promises everything that Option #1 offers. Unfortunately, I'm unable to get the admin interface to show up in my browser. (Is there a comprehensive solution to this? It seems that every web page on this that I tried was missing some important details, such as what settings to use in the /etc/nginx/sites-available/mydomain1.com page.)

Is there an easier alternative to the above two solutions for creating my own email server?

Unless I'm able to get one of the above two solutions to work, it looks like I need to use an outside email provider. Which ones offer catch-all emails for a domain? (I use x1@mydomain1.com, x2@mydomain.com, etc. to help with filtering messages.) I know that the documentation here lists Fastmail, Google Apps, and Outlook.com. Are there other options I should be aware of?

You can try installing iredmail and zimbra on your VPS. Zimbra has some extra nice features like shared calendar etc but it requires a minimum of 4GB RAM. Iredmail will be lighter, but it needs to be installed in a fresh VPS, not an already configured system.

For managed email hosting, apart from the providers you mentioned, you can also try using rackspace email.