The beginning of outer space and spaceflight is something hard to classify because the boundary between an atmosphere and the vacuum of space is very fluid. A space border is to be defined according to what one considers air and space / what one considers important in these matters. The space border may be an air pressure border rather than an altitude border, and should apply to all celestial bodies.
One of the following altitudes and pressures might be set as a border between an atmosphere and outer space / between air- and spaceflight (some of them are based on my personal spaceflight experience in Orbiter2016):
60,000 ft (18.3 km) The Armstrong limit above which the outside air pressure is so low that you need a pressurized suit (like a spacesuit). Water would boild at the temperature of your body. So your body considers the space above the Armstrong line to be vacuum and you can't survive without a pressurized suit or cabin anymore. 90% of the Earth's atmosphere's mass is below you. FAA airspace legislation ends at the Armstrong limit. The sky gets very dark already above 60,000 ft and you'd see the brightest stars and planets at noon. The Armstrong limit marks the begin of nearspace, a transition area between airspace and outer space. If you consider it the space border already, the following celestial bodies would count as bodies with atmospheres: Venus, Earth, Titan, and the four gas giants.
115,000 ft (35 km) The triple point of water. Above that altitude water can't exist in liquid state outside anymore. Water ice would sublime (evaporate), not melt. The triple point of water is at a pressure of about 611.7 pa (0.088 psi). At this altitude there's also the upper boundary of the ozone layer above which there's little block of UV radiation. Above that altitude the sky is completely black and won't get any more blacker. You'd see all bright enough stars and planets at noon (such as the Orion in summer). Jet aircraft can't fly leveled anymore and the altitude record for a jet plane is a MiG-25M about 8,000 ft (2.5 km) above that altitude. If you consider the pressure of the triple point of water to be the space boundary, you are to add Mars to the list of bodies with considerable atmospheres.
32 mi (51.5 km) The stratopause (stratosphere-mesosphere border). Temperature stops increasing and starts decreasing with altitude. Above 32 mi, air pressure drops below 0.01 psi. If you consider this or a lower altitude the space border, note that Yuri Gagarin wasn't the first man in space for you. The first man in space would be American pilot Joseph Walker who reached slightly more than 32 mi in the X-15 on 30 March 1961, a few days before Gagarin's spaceflight.
200,000 ft (61 km) As I conclude from flying in Orbiter2016, above about that altitude, pressure drops below 0.003 psi. There it is so low that you can't hear anymore, there is no sound and one is essentially deaf above that altitude. Outside only, since sound would still travel through your spacecraft of course. Also above circa 200,000 ft the ionosphere begins. Balloon flight is no longer possible. The highest unmanned balloon reached an altitude of 173,900 ft (53 km) and the highest manned one (flown by Alan Eustace) reached about 136,000 ft (41.5 km). Above 200,000 ft you may become weightless in your spaceplane without having to push the yoke. See this answer for clarification.
71 km (230,000 ft) This is circa the lowest perigee I reached in Orbiter2016 and continued orbiting the Earth. The orbit didn't change much, it remained pretty stable.
50 mi (80.47 km) This is the space border as defined by NASA, the USAF and the FAA. It is the mesopause (mesosphere-thermosphere border): temperature stops decreasing and starts increasing again. Pressure falls below 1 Pa / 0.00015 psi above that altitude. It is defined as where you have to put more effort into rocket-powered flight rather than air buoyancy. Astrodynamics take over from aerodynamics around that altitude. If you consider the space border here, you must add Pluto, Eris and Triton to celestial bodies that have a considerable atmosphere.
83.6 km (51.9 mi) Theodore von Kármán calculated that at that altitude the atmosphere becomes too thin to support aeronautical flight.
53 mi (85.3 km) This is circa where in Orbiter2016 my spacecraft starts to glow when re-entering from orbit. I suppose the Space Shuttle started to glow around that altitude too. I regain rudder control around that altitude.
57 mi (91.5 km) The original Kármán line: a vehicle's speed to generate lift must be orbital speed. Aerodynamic lift is 2% while 98% of the vehicle's weight is carried by centrifugal force. While circular orbits are impossible at that altitude, an spacecraft in an elliptical orbit can attain a perigee at 230,000 ft and remain it quite stable.
100 km (62.14 mi) What is currently referred to as the Kármán line and set by the FAI as space border. It is just the nextmost double-0-value in metric units in order to make the "Kárman line" "more memorable", lacking any basis in physical properties.
65 mi (105 km) In Orbiter2016, my spacecraft's gravimeter begins to read a more considerable g-force around that altitude when re-entering from orbit (or when having an elliptical orbit with a perigee reaching that low).
118 km (73 mi) Quote from Wikipedia 1: "In 2009, scientists reported detailed measurements with a Supra-Thermal Ion Imager (an instrument that measures the direction and speed of ions), which allowed them to establish a boundary at 118 km (73 mi) above Earth. The boundary represents the midpoint of a gradual transition over tens of kilometers from the relatively gentle winds of the Earth's atmosphere to the more violent flows of charged particles in space, which can reach speeds well over 268 m/s (600 mph)."
120 km (75 mi) This is where in Orbiter2016 my spacecraft starts to experience significant atmospheric drag when re-entering from orbit. If you set the space border at this altitude or higher, you must include Io into the list of bodies with considerable atmospheres.
400,000 ft (122 km) NASA's re-entry altitude for the Space Shuttle, defined as the beginning of more significant atmospheric drag.
93 mi (150 km) Above that altitude, a stable circular orbit is possible.
450 mi (700 km) The thermopause / exobase (end of collisional atmosphere). Above circa that altitude the atmosphere becomes an exosphere which no longer behaves like gas. The molecules don't collide with each other and are dispersed away from Earth by solar wind, reaching escape velocity. If you consider this the space border, you must include Callisto into the group of bodies with considerable atmospheres. You would also have to classify only the following flights as spaceflights: Gemini 10, Gemini 11, Apollo 8 and Apollo 10-17. All other spaceflights wouldn't count as any.
10,000 km (6,214 mi) End of the exosphere. Above that altitude there's quite an absolute vacuum. If you consider this the space border, only Apollo 8 and Apollo 10-17 would you have to count as spaceflights.
35,786 kilometres (22,236 miles) Geostationary orbit. While this has nothing to do with air pressure/density and vacuum, some equatorial countries claimed legal right on the territory up to the Geostationary orbit altitude.
As for me, I consider 200,000 ft (61 km) the space border. The least plausible to me are the one at 100 km and the one at geostationary orbit, due to the reasons written above.