iPhone Remote App Is Very Latent In Controlling Large iTunes Library
Doesn't surprise me at all. An iPhone doesn't have anywhere near enough memory to work with that much data unless the developer puts a huge amount of effort into making it work, and I can't see Apple doing so when few people have a database that big.

Most likely it can only store info about a small subsection of your library on the phone, and whenever it needs to access data from a song it doesn't have, it has to go back to the server. I could see that maxing out a fibre channel network's bandwidth, let alone wireless.

About all you can do is send an email to apple's support team and ask them to fix it in some future update. If enough people complain, they will.

Have you tried working with playlists that only expose small sections of your library?