Analyzing Jupiter

First off, since Jupiter doesn't have a surface, the 1 bar pressure altitude is commonly referred to as the surface. Surface temp (from a NASA fact sheet) is, in that case, around 165 K; cold but not cold enough that you couldn't insulate it trivially. So in this region, pressure and temperature are not a major concern. At this altitude and nearby you will get clouds of ammonium hydrosulfide, with water clouds also in denser areas below. These aren't really a problem, either.
Instead, what you need to worry about is the 100 m/s winds at this altitude. The wind speeds do vary by zone, so there are areas between bands where wind speed is near zero. A graph of wind speed by latitude illustrates this.

These wind speeds are in the jets, in the 0.7-1 bar region all the way down to at least 22 bar, which is as far as the Galileo probe got to check on them.
So a better solution might be to fly higher, above the clouds. At about the 0.1 bar zone (or 10$^4$ Pa on the top chart; 50 km altitude above the 1 bar level), the winds have mostly decayed away (they decay away in 3 scale heights, and a scale height is 27 km on Jupiter), and force on a craft from wind will be reduced by a factor of 10. Temperature is even lower at about 112 K, but with low air pressure and little wind, there won't be too much heat loss. Insulation should again be trivial.
So now we can handle pressure, temperature, and winds at this altitude, all that remains is to deal with the gravity. With low air pressure, floating will then be hard. In fact, it will be close to impossible. The atmosphere of Jupiter is primarily Hydrogen and Helium in the first place, meaning that hydrogen balloons won't float like they do on Earth. Even if you kept your balloon's gas filled envelope at a very high temperature, the density difference would be only marginal with the surrounding air. You could lower the balloon's envelop pressure to drop density further, but then you would need a rigid envelope, further increasing your required structural mass and making the balloon less efficient still.
More rigorously, the density of Jupiter's atmosphere at an altitude of 1 bar is 0.16 kg/m$^3$. If we can hold our balloon envelope at vaccuum, then we can lift 32 tons of mass per Hindenburg of volume. Unfortunately, that isn't really that much; the Hindenburg itself was more like 230 tons of mass. At 1 bar of pressure, the forces on an envelope held at vacuum will be tremendous, not to mention the shear forces from 100 m/s winds.
Finally, the biggest problem with your cruise ship idea is that your passengers will be crushed by the gravity. With gravity around 25 m/s$^2$, it will be much higher than on Earth. Not only will that make already-nearly-impossible floating even harder, it will probably kill all your passengers.
Other Gas giants

Saturn's atmosphere is similar to Jupiter's. In fact, the density at the 1 bar level is slightly higher (0.19 kg/m$^3$), despite its lower surface gravity (1.06$g$). On the other hand, its scale height is larger (52 km) and wind speeds are much higher, up to 400 m/s at the equator. Also, as you can see in its graph, its 'surface' is the 0.1 bar level, not 1 bar. This means that you will see the very high wind speeds at that lower pressure level. Thus, even floating at high altitudes with nearly zero lift, you still get buffeted by extremely strong winds.
Assuming you can survive the high winds at the 0.1 bar level, given the density of the atmosphere, a spherical balloon envelope 1 km in diameter will have a volume of about 0.5 km$^3$ and a lift of 9500 tons; enough for a tourist vessel. A full on modern cruise ship of 100,000 tons would require a spherical balloon of a little over 2 km diameter.
The other gas giants are considerably more iffy regarding data; Jupiter and Saturn have had the attention of Galileo and Cassini, respectively, for many years. Uranus and Neptune have not. NASA's Uranus fact sheet gives a very promising atmospheric density of 0.42 kg/m$^3$. However, wind speeds are not well known and could be up to 250 m/s. If there are lower winds speeds at this altitude, then this would decrease the volume of vacuum needed by a factor of 2. However, this really only reduces the speed at which you must wave your hands to make this a reality.
Conclusion: Wave many hands
On a gas giant with Jupiter's gravity, the only way to save your passengers is with some magical gravity canceling device. I would assume that having such a device would then make floating your ship trivial. But without hand-wavey solutions, not only can you not float in Jupiter's atmosphere, you will kill your human passengers trying to do so.
Other gas giants are less magic-requiring, in that surface gravity will be close enough to Earth's to not kill your passengers. However, the problems with floating in an atmosphere that is already made of helium, the least dense element, remain. Even at vacuum, you have almost no lift. The solution is materials of indeterminately high strength, in order to hold a (very, very) large envelope at vacuum against atmospheric pressure, while not disintegrating in the high winds. Just to be clear, given the forces involved in holding a cubic kilometer or so at vacuum against 1 bar pressure, this is nearly as hand-wavey as a gravity canceling device.
In fact, the larger the better. If you want to ensure the passenger's comfort, you will need the most mass and inertia in your balloon as possible to keep the winds from buffeting them uncomfortably. That means, you will need a vacuum chamber kilometers across; like a mini-moon floating in a Saturnian sky.