Tool steel, aka carbon steel, blades are not "stainless". W-2, 1095, L6, O1, A2, 5160, and M2 are commonly used tool steels. Generally speaking, these have better edge retention and are easier to sharpen than stainless steels. However, they rust. Very easily if you don't keep them dry and oiled.
D2 (used a lot by Benchmade) is refered to as "semi-stainless". It has superior edge retention to stainless (although it is rather difficult to sharpen), but it does corrode if not taken care of. Not as badly as a carbon steel, but it requires much more maintainance than a stainless steel.
In terms of edge retention, stainless steels are vaguely in this order (lower to higher): 420J, 440A/AUS-6, 420HC (might be out of place), AUS-8/440C, VG-10, ATS-34/154CM, S30V. The last 4 are very good steels, the current "top of the line". ATS-34 and 154CM are pretty much identical (Japanese vs USA), VG-10 is Jap, S30V is Yank. Keep in mind that a lot about the quality of steel is also in the heat-treatment that the maker gives the blade. 440C is a mid-level, but Benchmade does an extremely good job with it. Spyderco's AUS-6 is superior to anyone elses. There's other steels like BG-42, CMP440V, or ATS-55, but these aren't used to the quantities as the ones listed before, and have unique properties of their own (and each maker's knives are unique in how they deal with these properties).
CRKT uses a lot of AUS-6 and AUS-8 in their knives. To be honest, I've never been terribly impressed with any CRKT knife, but many people like them. The M16 line is very popular. The AUS-8 is probably only around 57-58 Rc hardness. The premium steels (VG-10, ATS-34, 154CM, and S30V) are usually hardened to 59-60. So pretty much any knife made from these steels will keep an edge better than your old CRKT.
In comparison, tools steels can be made harder, sometimes up to 65 Rc. But usually, they're not taken above 60-62. The harder you temper a steel, the longer it'll stay sharp, but the more brittle it'll get. Abrasive cutting can microscopically (or macroscopically) chip a brittle blade, as can accidentally dropping or bumping the blade against something. This is why you'll often see tool steel knives hardened to "only" 58-60. This makes a knife that'll stay sharp a very long time, and will be easy to sharpen.
For the best of both worlds, you'll probably get a lot of reccomendations for the Benchmade 710HS or 806D2 (thumbstud or thumbhole). These have black teflon coated D2 blades at 60-62 Rc. The coating prevents corrosion, and it'll take a wicked sharp edge for a long time (harder to sharpen though). You still have to keep the edge dry though, because it'll still rust, and corrosion ruins the edge-holding abilities of steel.