Do categorical features always need to be encoded?
You have partly answered this question yourself ("because converting to integers implies that there is an ordering between features").

I will just clarify the terminology a bit more.


Categorical data: information has categories, but no natural ordering defined between them (gender, name of user's cat)
Ordinal data: information has categories with natural ordering defined between them (annual income scale defined in terms of categories \$40000,   \$40000 - $80000).


If the variable is of type ordinal, you can replace it with integers and proceed with the algorithm. If it is categorical, it should be converted as well as encoded.

Hope this helps.