Your reference letters should be diverse and include 1) your program director; 2) someone well known within the field you are applying to; and 3) Someone who knows your work well and can comment. In some cases, eliminating the program director letter is ok, but many programs will ask for a letter from your PD. Of course, they say 3 letters but you can always send more, according to what everyone tells me. Only rare programs would refuse to consider a fourth letter if it added something to your application.
A lot of your letter will be based on your CV which you can provide to the bigwig writing the letter, and obviously you would want to meet with them to discuss career plans and why you are a good candidate, etc. Most likely if your program is like mine the attendings are constantly talking about residents to each other (this is not a bad thing, by the way), and they will all know that you do a good job even if they didn't see it directly.
For my fellowship letters I had program director + letter from the director of the fellowship here or head of the subdivision (not always the same person) + faculty who I did projects and signed out a lot with. I did not get a department chairman letter, it wouldn't have added much. The only way it would add much is if the chairman is in the same field. Having a letter from your program's director of notbloodbankology would be a better letter to have than a letter from the department chairman, unless you worked a lot with the department chairman.
The uniform finding on fellowship interviews that people say is that if you have a letter from a well known faculty member in the field and that letter is glowing, that is one of the biggest factors in getting interviews and getting the position (as well as your publication record). Fellowship directors trust known commodities, and if someone they know recommends you, that means a lot to them.
It sounds to me as though you already have one letter from a prominent and well known notbloodbankologist, so getting another one is not going to add much. But another letter from someone who knows you well will add more in this situation, because it covers areas not often covered in the first.