I don't even have a JRE setup on this computer (quite oddly I might add).
Packaging it alongside your game will probably net you some points in ease of use you would otherwise lose ;)
My 2 cents.
Yes the more I think about it, packaging a JRE is going to be the best option. Thanks!