17,000 companies * 10 characters for the average company name (est) = 170,000 bytes
170,000 bytes / 1024 = 166KB
166KB / 3KB modem connection = 55 second minimum load time
so by just including the complete list on one page the download will take a minimum of about 60 seconds to download for a modem users. this doesn't count the time it takes for the browser to parse and format the data. the more code you add to simplify the selection process (javascript & images take space) means a longer download for the user.
so you can either split this among several different pages (user waits for refresh), or make it easy to choose a company from one screen (users will have to live with a potentially several minute load time). ie select the first letter of the company then choose from all companies beginning with the letter "F". or users download a javascript/java "wizard" that offers auto-complete features.
compression might help to a limited degree. look at enabling gzip on the web server.