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.
14What is the difference between a boat and a balloon? Because you can float a balloon on Earth in the atmosphere, a boat in the ocean. Given the composition of a gas giant, a balloon might be more applicable. – kingledion – 2018-01-11T19:51:03.140
Yeah, a balloon is a viable option. The way that I classify "boat"/"ship" in this question is that it floats on its own due to buoyant forces, so a balloon totally checks that box. – Austin A – 2018-01-11T19:55:14.613
If we need to consider the chance of this ship being caught in a storm, it better be a very sturdy ship. Earth's hurricanes are nothing when compared to storms in Jupiter's atmosphere. – Alexander – 2018-01-11T20:05:23.363
36
XKCD Has a fantastic article on this very topic https://what-if.xkcd.com/138/
– Douglas – 2018-01-11T20:22:46.6373If you gas giant is like Jupiter, you can't make it significantly buoyant based on the type of gas as hydrogen/helium is the primary atmosphere the lightest possible gases. So you need to use hot hydrogen/helium as your lifting gas. A detailed answer will need to know the temperature and pressure to calcuate buoyant force and materials requirements unless everything is just hand-wavium. – Gary Walker – 2018-01-11T20:25:18.913
6You shouldn't accept an answer so soon. Give it at least 24 hours, the person with the best answer might be asleep right now! – kingledion – 2018-01-11T21:58:03.170
Good advice. Everybody did just assume Jupiter, which would make for a non-optimal environment. – Austin A – 2018-01-11T21:59:39.410
Although we could make a balloon, or even a vast construct like Buckmaster Fuller – Thucydides – 2018-01-12T02:15:37.297
1@AustinA I updated with more info on other gas giants – kingledion – 2018-01-12T09:47:49.833
@GaryWalker if you could come up with a thin/light material strong enough to hold its shape under pressure, then form a vacuum inside it, that could potentially work. Material would have to be some sort of unobtainium though – Baldrickk – 2018-01-12T10:53:34.773
1
And another relevant XKCD what if: https://what-if.xkcd.com/30/
– Residuum – 2018-01-12T14:18:40.660What do you mean by "float on a gas giant"? Like a traditional ship, floating on the liquid core, under dozens or hundreds of kilometers of atmosphere? Or floating in the atmosphere, somewhere? – HopelessN00b – 2018-01-12T19:38:21.910
I define floating not by the medium in which the vessel is in, but by its ability to counteract gravity via buoyant forces. – Austin A – 2018-01-12T19:49:10.090
Your biggest problem, other than getting there, will be the radiation. Jupiter is not a friendly giant. – J... – 2018-01-13T14:58:35.890