A ping sensor would see them, no matter what color they are.
That’s because black absorbs IR (and a whole host of other frequencies in the visible range - hence, black); a ping-style ultrasonic sensor likewise has issues with non-uniform surfaces, and more seriously with soft objects like pillows (or other sound-absorbing material).
There is no one “do it all” sensor for ranging, unfortunately (with the exception of possibly LIDAR coupled with extensive mapping and processing - not something that is cheap or even doable with only an Arduino). So you need to combine sensors and then integrate the data that they produce so your system can gain a better idea of what is “out there”.
As far as “cheapest”:
Maybe not for the time it would take you to modify, but one of the best ultrasonic sensors you can get for very low cost is the Polaroid ranging module. Acroname sells these as kits, and they aren’t cheap - but the same type of sensor was used in the old Polaroid cameras, and they were a favorite of hobbyist robot builders in the 1980s. You can still pick up such cameras in thrift stores if you look carefully, for generally a few (USD) dollars. Look for “Sun 660” or “Spectra” (there are other models that used them).
As I said, though, you have to do a bit of work to hack them to work with the Arduino; you can find articles on the Seattle Robotics Society website that detail this process, but the process won’t work for the Arduino. The author of those articles, though, recently wrote an article for Servo Magazine (I think it was the June issue?), detailing how he converted his original hack to work with the Arduino. The only other issue with these units is that they tend to use a lot of power when pinging; up around 1A of current or so. They are meant for distance and accuracy, though, like what you would see when taking a photo. They have a fairly narrow cone (about 15 degrees to either side), too.