The trick is the difference between intrinsic and extrinsic curvature.
Intrinsically curved spacetimes are curved relative to their own coordinate system. On intrinsically curved space(times), Euclid's laws, in particular, the parallel postulate, are not valid, and the geometry is necessarily different. Mathematically, there is an object called the Riemann tensor that (in one interpretation) measures what happens when you parallel transport a vector around a closed loop in every possible direction, and says "hey, you're not necessarily brought back to yourself!"${}^{1}$. There are many ways of detecting intrinsic curvature, but this is a first idea. Note that, contrary to your intuition, the 2-d sphere is intrinsically curved, and not flat, as shown in the footnote.
Then, you have extrinsic curvature. This describes how something curves in some enveloping space. Imagine a sheet of paper. You can curve this sheet into a cylinder without distorting it. An ant living on the sheet of paper would not and could not know if it was a flat paper or a cylinder without "going around the world" or looking out into the third dimension somehow. A cylinder is not intrinsically curved. Its curvature depends solely on the way in which it is fit into 3-dimensional space. There are several ways that we can detect this, but the simplest is to "look to see if the normal vector to the embedded space moves around relative to the bigger enveloping space". But note that this definition directly appeals to the enveloping space. You can even construct examples where a given 2-d space will have extrinsic curvature relative to some enveloping spaces, but not others.
${}^{1}$ If you are skeptical of this talk, imagine an arrow sitting at the equator in Africa pointing directly north. Take this arrow along a meridian , not changing its heading, until it hits the north pole. Now, take it back down to the equator, this time, hitting south america somewhere. Now, parallel transport it back to its original position in Africa. It's no longer pointing due north, right? This is because the globe is intrinsically curved.