A letter of recommendation or a language evaluation is not just a way for a committee to see that someone thinks you are great in general. It is instead a specific opportunity for someone who knows you well to say that your plans fit with who you are and for a relevant expert to confirm that your project is sound and that you are qualified to take it on.
Remember that your recommender or language evaluator can also be a great resource for guidance and support. Have conversations with potential recommenders early on. Not only will this give you a chance to take advantage of all their feedback, but it will also give your recommender time to write a strong letter or your language instructor a strong evaluation, based on specific knowledge of your proposal.
Asking the right people is key. Don’t just think about who knows you best, but rather who’s in the best position to serve as a kind of expert witness in support of your proposal: appropriate expertise and first-hand knowledge of your relevant background/preparation make all the difference. (An English professor might know you very well after Daily Themes, but probably isn’t the best person to persuade a committee that you can do great work in a Chemistry lab… Someone who hasn't taught you since your first year as an undergraduate might not be in the best position to persuade a committee that you're well prepared to embark on graduate work...)
For language evaluations, of course you'll want to go first to someone who has taught you in that language recently, ideally at Yale. If you haven't studied a language at Yale, but with someone elsewhere: might that person be willing to do a language evaluation for you? Even if you haven't studied a language at Yale, you may still be able to get a language evaluation from a Yale language instructor, especially for a postgraduate fellowship, as long as you ask well in advance. Start by contacting the relevant department or the Center for Language Study to see if someone there might be able to help: for a list of languages taught at Yale and where they're taught, see here.
If you have the option or requirement for more than one letter or language evaluation, you'll want to think about how they complement one another and your application. Two letters from the same laboratory, for example, might say similar things and not give as helpful a range of information about your preparation to undertake further research in the field as a letter from someone in the laboratory complemented by a letter from someone who taught you in a relevant class. Similarly, a language evaluation attesting to your ability to pursue a project in the primary language of the country to which you hope to go is terrific, but if other languages are also spoken there and having fluency in one of them would help with your project it might be helpful to get an evaluation which addresses that additional ability.
Get to know them and let them get to know you. Discuss your larger interests and goals. Ask for their advice about potential projects, readings, courses of study, graduate programs, etc. These conversations will be invaluable in themselves, but they will also allow you to judge who is likely to be your most enthusiastic recommender. These meetings will also allow those who write letters and language evaluations for you to write more informed and more personally engaged letters or evaluations that discuss what makes your proposal not only feasible but also worth supporting.
Three to four weeks may be adequate, but it is helpful to consult with the recommender or language evaluator to see how much lead-time is needed. This is especially true for letters and evaluations for major fellowships, letters and evaluations to be written over breaks, and letters and evaluations needed for popular deadlines.
"Do you feel you know me (my relevant language skills / my academic record / my leadership qualities / etc.) well enough to write a strong letter of recommendation / language evaluation for the X fellowship?"
By asking this question, you've given someone the opportunity to decline gracefully if they need to for any reason. If the answer is "no," don't push.
In addition to meeting with your recommender or language evaluator as an adviser and to discuss your plans, it is a good idea to discuss the specific fellowship to which you are applying, what you're proposing to do with the fellowship, what makes you a good candidate, and what the committee might be looking for. Bring to this meeting:
Tip: Write your recommenders and language evaluators a note of thanks—and don't forget to let them know what happens.
You may ethically provide a list of bullet points you would like the letter to address and/or a factual narrative of key achievements (avoid adjectives)—along with other supporting information (such as listed above). Explain that you are unable to write a draft that provides the kind of judgment and comparative evaluation that only the recommender can provide and that helps make for a strong recommendation. You may refer them to this website.