Your definition that circles are perpendicular if their tangents are perpendicular is appropriate.
The answer to your first question – "is it possible to create four circles on a sphere, $a$, $b$, $c$, $d$, so that each two circles are perpendicular to each other?" – is yes. Circles of latitude and longitude meet at right angles, for instance. Such "quadrilaterals" are never radially symmetric, though, so perhaps that's not quite satisfactory.
Imagine, then, a square pyramid intersecting your sphere, with its apex centered above what I shall call the north pole. The angles of the circles around the north pole made by its face planes are acute. As we move the pyramid downward, the angles increase, approaching the angles of the base, which are right angles. Unfortunately, the limit is reached precisely as the apex reaches the north pole, where the circular segments vanish. However, note that there is another circular polygon cut where the face planes reemerge from the sphere. The angles of this polygon are equal to the angles of the polygon about the north pole. So, when the apex reaches the north pole, these angles are all right angles.

What we have proved is that the face planes of square pyramid with its axis on a diameter of a sphere and its apex on the sphere cut four perpendicular circles in the sphere.
The answer to your second question – whether we can create such right-angled "polygons" with any number of sides – is also yes. We can also use pyramids to see this. Consider a right regular $n$-gonal pyramid for $n \geq 5$ intersecting the sphere like our square pyramid. If the apex is placed so that the lateral edges of the pyramid are tangent to the sphere, then the circles of intersection will make angles of measure zero with each other. As we move the pyramid down, the angles increase. As the apex approaches the north pole, the angles approach the interior angles of the polygonal base, which are obtuse. So, somewhere in between, the angles must be right angles.

That's an intuitive argument with some unproved assertions, but it isn't difficult to make it more precise, depending on the level of rigor you're wanting.
Note, incidentally, that the answer to all your questions is no if you're requiring the circles to be great circles, that is, circles whose centers are the center of the sphere. Such circles are the "lines" of spherical geometry.