Linear regression is a good place to start -- it trains quickly and works well with small amounts of data. Categorical inputs aren't a problem; one-hot encoding will learn weights for each value.

That said, linear regression isn't always best, and it depends on your data.