It sounds like you're doing everything right; 480x360 and at 72dpi.
I'm not familiar with Lightroom. Is there a Save/Export to Web/Devices function?
This function is available on other Adobe products, so I would assume it's available on Lightroom.
It will allow you to maximise compression and get the best file size without compromising the quality too much.
The only other thing I can think of is that your memory card has a slow read speed.
To test this you could try transferring a few images over to the device memory and see how quick you can scroll through them.
If you find that they are quicker, then you may want to invest in a memory card with a higher class.
Also, having a very large amount of photos will increase read time, as thumbnails will have to be created/read.
[edit] Transferring your photos directly to the memory card (drag and drop) is by far the quickest and most efficient way of getting the photos onto your Blackberry.
