Negatives that print well at the equivalent of grade "2" are not problem negatives - they are normal negatives. So I wouldn't be too worried about them.
A diffusion light source works really well with contrasty negatives, and helps with dust too.
A dichroic colour head makes an excellent diffusion source, and includes contrast adjustment as well. So if you find something that offers that, don't be dissuaded by its suitability for colour.
There are/were many enlargers that offer interchangeable light sources. You can even buy Beseler enlargers new that offer that, but they are quite pricy.
Ease of local availability of things like accessories tend to motivate my recommendations, but if you are willing to look worldwide, that may not be as important for you.
I've always liked the medium format Durst enlargers - the M601 and the like. When they were in production they were more common in Canada and Europe than they were in the USA, so that affects current availability.
Be careful about bulb requirements. There are a few enlargers that take hard to find bulbs.
Don't reject out of hand a 6x7 or 6x9 capable enlarger. They handle smaller formats well.
I would suggest wandering through the new and used equipment pages of KHB Photografix' website. It is full of information. They also sell new and used equipment, but their used prices reflect the fact that the equipment has been fully serviced and is supported by a warranty. Note that being based in Canada, prices in their online store are in Canadian dollars.
Here is their website - a great information resource:
http://www.khbphotografix.com/