The organization I work with has used NOLS Wilderness Medicine Institute for training in Wilderness First Aid for several years until this past one when we switched to American Red Cross's Wilderness & Remote First Aid course. We have our own staff that are now ARC instructors is the reason for the switch. I can honestly say that NOLS WFA compared to ARC WRFA is very, very similar. There are some different takes on how to handle certain situations, and in some ways WRFA covers more material. However you can't go wrong with either one as they both will teach valuable skills. Both are essentially two day courses and require a current CPR certification for your certification to be valid (it can be taken after the WFA course.)
I noticed you linked to the Wilderness First Responder course on the NOLS site. I can't speak for that level of training, since I haven't taken WFR yet, but hope to do so before next summer. Though I can say this: I know and have worked with several people with WFR certifications through NOLS WMI and can vouch that they are very well prepared to handle backcountry emergencies. An important thing to note is that ARC doesn't offer an equivalent to WFR.
I don't have any experience with SOLO or Wilderness Medical Associates so I can't compare those, but I'm sure they are excellent organizations as well.
You first need to decide what level of training you want to get. That will help you decide which organization to go with. If you're just testing the waters or just want a solid foundation then I would recommend taking a WFA course. You can still go up if you think you need more training later and it covers a lot of material. However if you are out in the middle of nowhere quite often and you plan an being very prepared then I recommend taking a much more involved WFR course. If you're in the outdoors for a living then WEMT might even be something to consider, although it also involves becoming an EMT.