Too much choice is no choice.
You will not be able to tune up GWT Listbox/ValueListBox for purpose of displaying such huge amount data ( i am guessing entries in 1000's considering 20 seconds i.e 30% of 1 min). GWT Listbox is meant for selection. You cannot expect user to see 1000's of values , scroll and then select. Its a User Interaction nightmare.
The right approach is use to Async loaded SuggestBox for such huge data. With SuggestBox you can filters and display lesser data as choice based on users input keys.
If using SuggestBox is not feasible you must give a try for CellList in Cell Widgets ( they might show better performance ) - https://developers.google.com/web-toolkit/doc/latest/DevGuideUiCellWidgets
I am not sure but give GWTChosen a try - http://jdramaix.github.com/gwtchosen/