Hi, Mitch, and welcome to WMW! You are right - if the link is difficult to find, you'll get a less welcoming response from a potential link partner.
My suggestions would include:
Do a well-organized link directory with topical pages of links (as the numbers grow). Provide easy navigation to each link page by topic. Make the links attractive, and include a site description, not just a URL or site name link. Be sure your links pages are easy to find from your home page.
My personal list of link-page irritations (I've seen all of these from people requesting a reciprocal link):
1) Too many links - a page with 400 links is not going to be useful to anyone who stumbles across it.
2) Buried links page - webmasters send a URL, but I can't find a way to the URL from the site's home page (without running a site tool like Xenu).
3) Disorganized links - people create a links page with no organization at all; again, this makes it almost useless to the visitor who finds it.
Note that if you are getting a link from a high PR site, you may find the link desirable even if the setting isn't too great. Nevertheless, I'm not bashful about rejecting link requests and telling the webmaster why.