You should always implement some form of throttling on login attempts — even with the random words trick, it's not really practical for many people to memorize a passphrase with enough entropy to be secure against an unthrottled dictionary attack, especially if they need a separate one for each site they use.
(There are ways around that on the client side, like using a secure password wallet to store the per-site passwords, with a single strong passphrase to access the wallet, but for various reason they haven't caught on widely yet.)
It's also worth noting that a determined attacker can DOS your site just fine even without login throttling. The throttling, if carelessly implemented, just makes a particular kind of targeted DOS attack easier. To mitigate this effect, I'd suggest at least the following steps:
Set up a fairly low per-IP login limit, as well as a higher per-site one. This means that an attacker must must employ multiple computers with different IP addresses to effectively DOS your site, which, while certainly possible, still presents a speed bump. (You may or may not also want a per-user limit; it makes sense if you expect dictionary attacks targeted at single users, but in many cases a typical attacker would be just as happy with the password to any account, in which case their best strategy is to attack them all in parallel.)
When the limit is hit, log it. If it keeps being hit repeatedly, alert the site admins — whether it's a DOS attempt or a genuine dictionary attack, they'll want to know about it.
Make sure you provide an alternative way for users to contact the admins if they can't log in due to throttling.
Last but not least, require an anti-CSRF token on all login attempts. You'll want to do this anyway to protect against login CSRF, but as a useful side effect, it also stops certain kinds of simplistic distributed attacks (such as crafting a direct link to the login script and including it as an image URL in widely read forum posts).
Ultimately, IMO password length and form requirements are a red herring, at least from the site admin's viewpoint: if you let your users choose their own password, some of them will choose weak ones no matter what. If you require alphanumeric passwords with punctuation, some users will choose "abc&123"; if you require four-word phrases, they'll choose "I love my mom".
You can either accept that and find ways to live with it, or, if you can't or won't do that, take the choice away from your users and generate random passwords for them. In which case I'd very strongly suggest using the "four (or more) common words" method, since it yields much more memorable passwords for a given amount of entropy than, say, picking random characters or syllables.