I use Joomla pretty exclusively, and no I don't think it's hard to set up correct SEO on it.
Some things to note that you might want to change from the out of the box settings:
Not a great page speed on most free templates but nothing you can't change with a basic knowledge of CSS. (I build my own templates which takes an hour or two).
SEF URLs, I use sh404sef as mentioned by motron, and I use .htaccess rewrites.