This is a difficult problem! I'll try to break it down into the elements that I see as most relevant: how "difficult" are you, and how "difficult" do you seem? I've tried to keep the situations and skills general, but it's hard to talk about without more concrete examples. If I've erred in focusing too much on a specific situation please let me know and I will try to distill out the general bits more clearly.
The main thrust of my advice is that being proactive about expressing your limitations, extra-open to compromise where it's possible, and being prepared to do what it takes to make things smoother for others (again, where possible) are likely to help a lot. Feel free to assert what you need, but recognize that demanding that your needs actually be maximally met, all the time, can be a way to legitimately earn a label like "difficult". Being assertive is not the same as actually getting what you want/need.
1. How "difficult" are you?
The quotation marks are because difficult is a subjective judgement, but the underlying events that drive making that judgement are a bit more cut-and-dried. My writing is not perfect, so I'm explicitly declaring here that I am not applying any moral assessment of anything that follows in this section. Any appearance of such is me failing to express myself clearly.
This will vary by specific situation, but ultimately if you are hard to please then demanding (or appearing to demand) your preferences can reveal that. If 95% of the restaurants your coworkers suggest are unacceptable to you, then, regardless of reason, accommodating your desires simply is challenging for them if they want to eat with you. They can either limit the restaurants they are considering, or go without you.
There are things about your needs that I can't know or guess at. If you are deathly allergic to shellfish, but your coworkers really want to go to a restaurant that serves only shellfish, then obviously that isn't going to work. If, on the other hand, you can eat shellfish and you simply prefer something else one day, then a compromise might be possible in which you don't get your maximum preference on that day.
All of this is to say that it's not necessarily just a labeling issue. If it is, in fact, difficult to choose a restaurant that's acceptable to you, then there may not be a way to satisfy your needs which doesn't reveal that.
What can be done?
If you have a lot of restaurants or foods that are absolutely unworkable for you then obviously you'll have to avoid them. But because you may have more of these than many people, accommodating your needs may be more burdensome than accommodating others' needs. Offsetting this means you need to be more flexible than others might be when you can. If you veto several restaurants because you cannot eat there, then it may be reasonable for you to accept a restaurant where you can eat, even if you're not especially in the mood for it that day. Every suggestion after a veto is already them compromising for you, and that's worth keeping in mind.
And there will be cases, at least some times, in which the best thing you can do will be to remove yourself from lunch that day. If you've rejected X suggestions the group was otherwise open to, then you have become the obstacle to lunch that day. This perception gets stronger as X gets larger. If you ultimately settle on a place to eat, but your coworkers are not excited about it, then they will associate their mediocre lunch experience with accommodating you. These are directly contrary to your goals, and so if a good consensus choice for a place to eat is not forming then it can be worthwhile to remove yourself as an obstacle:
It seems like we're not at all in the mood for the same stuff today. I don't want derail everybody's lunch, so why don't you guys go on to [the top pick among them], and I'll catch you next time?
All of your needs and preferences still exist with this approach, and are not violated or compromised, but by removing those things as obstacles to what your coworkers want to do you stop being "difficult" and instead become are a good experience for the group.
2. How "difficult" do you seem?
You probably have a solid understanding of what foods you can and cannot eat comfortably, what leeway you have in compromising, and other factors which apply to these situations. Other people will not. So coworkers can't be expected to know the full list of relevant details and will instead just notice the outcomes.
If your coworkers don't know why you're saying no, they can't reliably give better suggestions or contextualize your vetoes. They'll just know that you are saying "no" to a lot of suggestions, and if you're often the lone "no" vote in the group then it will make clear that the group could have chosen a restaurant already, maybe several times over, if not for trying to accommodate you.
There are a few ways you can handle this. The more readily-understandable your needs, and the more "accepted" they are as needs, the more you can expect coworkers to at least try to take those into account. Going with the shellfish allergy above, if your coworkers know that you will likely die if you try to eat at a restaurant serving shellfish then they will (hopefully!) not suggest such a restaurant. If they only know that you reject all seafood restaurants, and don't know why, then it might be cast as a preference and earn you the "difficult" label:
I'm hungry for Red Lobster, but Rainbacon never wants to go there!
What can be done?
- Track how often you say "no", both in specific encounters and over
time.
If you are the one rejecting broadly popular choices significantly more often than others are rejecting choices, then you can easily gain a reputation as "difficult". And when you do say "no", follow up with something positive if possible-- a suggestion that you liked, or some guidance about what you're open to. Make it easier for people to provide a suggestion you can approve.
- Try to get ahead of needing to say "no" by providing information on
what you can't do
If you have a shellfish allergy, letting your coworkers know should prevent a lot of suggestions for seafood restaurants. Being told an arbitrary "no" feels very different from deciding not to make a suggestion because you know someone else can't or won't accept it. Help them determine what you might say yes or no to, so that their suggestions can take that information into account.
- Make your own suggestions
I assume you already do this, it's a good way to break the cycle of people submitting suggestions for your approval and then being denied. Depending on how restrictive your needs are, it might work better to suggest places that you know are popular with your coworkers rather than your own favorites. As above, they are already compromising by accommodating your rejection. If everyone else is getting their sixth choice, it is not really reasonable for you to get your first choice. Certainly not often.
- Be quick and earnest in supporting suggestions that you're OK with
If someone else makes a suggestion that works for you, support it! Whether or not that's the place that's picked, you saying "yes" is an important balance to when you need to say "no". Again, it doesn't have to be a suggestion you're really excited about, it's vital that you be seen making an effort to get to "yes" when you, alone, are also seen issuing a lot of hard "no"s.
I've not discussed anything about the recruiters here because I think that that situation is very different from the coworker/lunch situation. The latter is an ongoing social interaction with no particular end point or goal for anyone involved, while the former is a professional interaction with a profit motive for the recruiter and a running cost-benefit calculation they are making.
It's the recruiter's job to find job opportunities that interest you and that you fit well, but they have strong incentives to send you more jobs than fewer. Any job you take will get them their commission, and no matter how many leads they send you're only going to accept one of them.