K-type is one of the best options for this. You really need the converter board. A MAX31855K chip is very easy to interface with. Sparkfun sells them mounted on a board for $15. For $4 more you can buy the special K-type connector to plug in standard thermocouple plugs. (These connectors are actually pretty rare parts. You don't find them in most electronics stores, even very big ones.)
Also look at a PT-100 RTD sensor. Use a MAX31865 for this. They are really easy to buy although finding ones with a specification below -55C is a little rare. The textbook says that the platinum sensors are good to -190C but the ones you can actually buy have a plastic case or some other limitation on the coldest temperature.
I would stay away from any analog amplifier. The process of amplifying the signal from either sensor up to the levels that the Arduino can read is actually more difficult and subject to more errors than buying the proper chip in the first place.
J-type thermocouples are slightly better than K at low temperatures but the prices rapidly get into the hundreds of dollars because they are so much rarer.