What is the lowest resistance pot that is useful with an analog input?
Assuming you wired it correctly (ie. you put the wiper to the analog input) your first setup looked like this:



Your big problem here is the current flow through the pot. Using Ohms Law the current would be:

I = V / R
I = 5 / 25
I = 0.2A  (200 mA)


That is too much to be drawing from the 5V pin and it could easily drag down the voltage to the rest of the board. Also the power would be:

W = I * V
W = 0.2 * 5
W = 1W


One watt is a lot to put through a pot, and you may well have burned the track inside it.




  So, if I included a 10k resistor on either side of the pot that should address the current issue but it leaves the question of whether the remaining 25-ohm range is too small for the ADC to register distinct values, ...


The 10k resistor will stop the current problem, but now the range in the voltage divider will be ridiculously small. The setup will now look like this:



Unfortunately the range you are going to read with the analog input is going to be (voltage divider formula):

Vout = Vin * (R2 / (R1 + R2))


With the wiper at one end R1 will be 10000 and R2 will be 10025 and with the wiper at the other end it will be vice-versa. So the voltage you get will be:

Vout = 5 * (10000 / (10025 + 10000))
Vout = 5 * 0.499
Vout = 2.497


Or:

Vout = 5 * (10025 / (10025 + 10000))
Vout = 5 * 0.501
Vout = 2.503


In other words you will always be reading about 2.5V and therefore your analog read will always return around 512, which won't be much use to you.




  I'm going with a larger value pot (10k or 25k) ...


That sounds like a sensible value. A 10k pot will only draw:

I = V / R
I = 5 / 10000
I = 0.5 mA


That is a reasonable current draw and the analog input will still read it fine.



As Majenko points out in his answer you don't want a whole lot more than that resistance because of the optimal input impedance of the ADC converter (10k). A very high resistance would mean only a small current would flow into the analog input pin.



How to use your 25 ohm pots

If you want to use your existing 25 ohms pots because of their physical appearance, then a  small resistor in series could reduce the current to a reasonable amount and still give a good reading range. For example, 330 ohms on the "high" side (and nothing between the low side and ground).

Vout = 5 * (330 / (355 + 330))
Vout = 5 * 0.193
Vout = 0.963


Or:

Vout = 5 * (355 / (355 + 330))
Vout = 5 * 0.581
Vout = 2.591


That is now going to give you a reading between 0.96V and 2.59V which, whilst not the full range of 0V to 5V should give you reasonable differentiation as you turn the pot. And the current through it would be:

I = V / R
I = 5 / 355
I = 0.014A (14 mA)


Thus the power would be:

W = I * V
W = 0.014 * 5
W = 0.070 (70 mW)




References


Voltage Dividers tutorial
Ohms Law