Everything you want is built into every major CMS or there is a module/plug-in that does this with a simple install.
>Support large number of users witout dying
Most CMS will have some level of caching, and will scale okay. The Onion runs on drupal, for example. One thing to keep in mind is that more important than the CMS you choose is what you do with it. If you have lots of registered users online, that will take a lot more server juice than anonymous users, because the CMS won't be able to cache as many elements. If you have a "who's online" feature on each page, that can add a significant load as it looks up all those nicknames for every page request. Does it cache image thumbnails or generate them on the fly every time? Et cetera.
>Good and simple WYSIWYG editor
For most CMS there is some option along these lines, often TinyMCE. These editors all have some serious limits (i.e. not such clean code), but they do fine as long as you disallow stupid stuff (H1 tags, for example).
>Customizable template for 'User' pages
Every CMS available will have this if you mean that the designer can customize the template. If you mean that each user can customize her own pages, I'm not sure. Drupal has some modules that allow for a lot of flexibility on the Profile pages.
>User pages viewable by non members
This is a matter of how you set the permissions. I would say all will allow this. The question is how good the CMS is at disallowing certain content. For what you're asking, it should be a simple switch (it is in drupal).
>Image upload + image optimize
Quality varies, but generally available on all CMS if by "optimize" you mean resize and apply some basic adjustments. Only a human can truly optimize an image.
>Ability to include Google Adsense on every page
Generally a templating matter, but some CMS have special modules that do things that allow you to add Adense inline, but make sure that you don't go over your 3-unit limit when on "list" pages.
>Approval or rejection of all pages after any change
Again, generally available I think, especially on the rather simple level you mention there (some admin with approve/reject authority). Some CMS designed for a corporate environment have a lot more granularity and allow more complex workflow. For complex workflow in Drupal, you would need to use the workflow module.
>Approved pages automatically added to directory style menu - viewable by non members
Generally available and sometimes themeable (e.g. the Drupal "views" module lets you theme this pretty much any way you want: blog style, a table-based view that allows you to sort on any column, etc).
>"Reasonably priced" .. Open Source GPL is always better ;)
- Drupal (OS)
- Joomla (OS)
- ModX (OS)
- Expression Engine (not free but cheap)
Install a few. Play with them for a bit. Choose the one that seems closest off the shelf.