What algorithms require one-hot encoding? I'm never sure when to use one-hot encoding for non-ordered categorical variables and when not to. I use it whenever the algorithm uses a distance metric to compute similarity. Can anyone give a general rule of thumb as to what types of algorithms would require non-ordered categorical features to be one-hot-encoded and which ones wouldn't?
 A: Most algorithms (linear regression, logistic regression, neural network, support vector machine, etc.) require some sort of the encoding on categorical variables. This is because most algorithms only take numerical values as inputs. 
Algorithms that do not require an encoding are algorithms that can directly deal with joint discrete distributions such as Markov chain / Naive Bayes / Bayesian network, tree based, etc. 
Additional comments: 


*

*One hot encoding is one of the encoding methods. Here is a good resource for categorical variable encoding (not limited to R). R LIBRARY CONTRAST CODING SYSTEMS FOR CATEGORICAL VARIABLES

*Even without encoding, distance between data points with discrete variables can be defined, such as hamming distance or Levenshtein Distance
A: 
Can anyone give a list of what algorithms would require categorical features to be one-hot-encoded and which ones wouldn't?

AFAIU, it has to do more with the particular data, less with the particular algorithm. Specifically, it depends on whether there is some meaningful order in the categories or not.
Consider two cases. In the first you have the categories bad, meh, good, and in the second you have apple, orange, pear. There is a natural order in the first case, because meh is probably in between bad and good, but probably nothing similar happens in apple, orange, pear. 
If you avoid one-hot encoding for the first case, you're "losing" the information about the order. If you use one-hot encoding for the second case, you're assigning some order to the categories that is not naturally true.

I do it whenever the algorithm uses a distance metric to compute similarity.

Why? Suppose one of the features is a categorical bad, meh, good, and you have three instances, 1, 2, and 3, where they are identical, except that 1 is bad, 2 is meh, and 3 is good. You probably want to express to the algorithm that 1 is more similar to 2 than it is to 3.
A: No machine learning algorithm requires  one hot encoding.  It is  one method for dealing with categorical variables. Dummy variables is another.  Traditionally, dummy variables was the preferred solution. For example, the R function lm() automatically creates dummy variables for categorical data.  If you are using python and scikt-learn then I believe many of it's algos require one-hot encoding of categorical variables. I believe that tensorFlow also requires one-hot encoding.  These are choices of how the variable is encoded.  There is no reason why dummy variables couldn't be used in the code instead.  This all has to deal with the actual code implementation of the algorithm. 
As hxd1011 points out the issue of describing the 'distance' between categorical variables is a delicate issue.  In addition to the distances mentioned there is also Jaccard distance.  Some ML methods, particularly SVM's are inappropriate for categorical data and adding categorical variables can/will (either, both, you decide) lead to models with very poor predictive power. Most ensemble models handle categorical data 'as is' and require no pre-processing. 
