Well, to be honest, Verizon isn't a good choice for J2ME.
1. They use the Brew OS, so getting Java on a phone is not as easy. 2. In order to get your J2ME application on your phone you have to use Verizon's service, which costs.
The Best J2ME phones are usually on Cingular or T-Mobile. But don't get as good coverage as Verizon. Nokia, Motorola, and Sony are the leaders in J2ME phones. Siemen's and BenQ are also good, but can't be found in the US.
So Nokia has the 6600 series which is really good smart phones, Look at Nokia's developer website for more info on Series 40, 60, and 80 phones and what they mean. Motorola's motocode website is their developer site that has more info too.
Go to sun's Java site, click on J2ME and devices and they have a spreadsheet on devices and their features.