Sorry but I guess you are asking me to write this.
500 items should sort in half the time of 1000 items. As to the iPod the only time you find folk that push back on that is when they have a personal grudge or issue with Apple, iTunes, Windows or who knows what.
You know to just nod and let them carry on.
There's also those that have the "correct order" issues. I have never seen that to be a problem yet you can read long diatribes about it out there. Here I'll rename or such as need be. Since I'm a programmer this seems pretty trivial but that's unfair as many folk don't want to dive in.
Sorry but something is off here. Divvying up the playlist to a few seems like an easy workaround but then again you encounter folk that won't do that.