A HSM will not avoid complexity; rather, it will add quite a lot of complexity to the whole system.
What HSM do best is key storage: the key is in the HSM and does not get out of it, never. However, you still have to worry about the key life cycle. With a "software" key, stored in a file or in the entrails of the operating system, backups are a vulnerability (you don't want to have many copies of the key floating around). With the HSM, this vulnerability is avoided, but backups become a major headache: losing the key is also a major risk, especially for encryption (if you lose the encryption key, you lose the data). So that's a first item to look at for HSM: backup procedures. I have some experience with Thales (nCipher) HSM, which do it like this: the keys are actually stored as encrypted files (which can be saved just like any file), and the decryption key for that key can be rebuilt with a quorum of administrator smart cards (within a new HSM).
HSM rarely do bulk symmetric encryption. It does not make much sense, actually, to do symmetric encryption with a HSM: you use encryption because the data is confidential. Logically, if the need for secrecy is such that the symmetric key must not leave the HSM, then the data itself should not leave it either. Also, symmetric encryption means that both encryption and decryption use the same key: if that key is in the HSM, then encryption and decryption will both have to go through it.
HSM are better used with hybrid encryption: the HSM stores and uses the private key of an asymmetric encryption system; when data is to be encrypted, whoever has the data generates a random symmetric key K, encrypts the data with K, and encrypts K with the public key corresponding to the HSM-stored private key. In that sense, HSM operate as (oversized, overpriced) smart cards.
Of course, there is another extreme, in which you fit your entire application within the HSM. This requires a programmable HSM, and that's a completely different context. Thales HSM allow that as an option (it's called "CodeSafe" and "SEE"), which they don't give away for free... and don't expect running traditional code in that. HSM have crypto accelerators, but they are otherwise fairly limited embedded systems (think 60 MHz ARM CPU at best: HSM shielding is at odds with heat dissipation). You can fit relatively complex code in a HSM (which allows for it) but it is a specific programming effort. Also, some HSM don't allow it at all.
Though HSM are expensive, the biggest cost in a HSM is operations: they entail a lot of procedures for installing, configuring, operating, restoring and retiring. You will need people. My main criterion would then be: procedures. A good HSM will come with a detailed usage manual which describes how things should be done. It's not the hardware which matters, but how you use it.
Certifications, like EAL 4+ or FIPS 140-2 Level 3, may be required for regulatory purposes. You rarely choose whether you need it or not; that's a requirement from the intended usage context. Obtaining such a certification is a very long and expensive process, so you won't do that by yourself. On the other hand, you might want to broaden your shopping area: if HSM are mainly big smart cards, smart cards might be usable in lieu of the HSM. A 20 EUR smart card can be FIPS 140-2 Level 3; it will compute only one RSA-2048 decryption per second instead of 500, but that may be sufficient for you.