The question concerns what kinds of curves deserve an implicitly exact representation rather than a discretized approximation. The crux of the matter is this: to be successful, the class of curves you support in this manner must be closed under the class of curve- and polygon-creation operations supported in the GIS.
These operations include:
Buffering. In this process, you need to construct curves that are parallel to features. ("Parallel" means in the sense of maintaining a fixed distance.) This includes circles and portions thereof (for buffering points), oblique parallels (which are curves equidistant to geodesics on the spheroid, and can reduce to isolated points in special cases), and concentric circles. On the sphere (but not, generally, on an ellipsoid) the oblique parallels are themselves circles.
Polygons of influence (Thiessen polygons; Voronoi polygons; Dirichlet cells). To construct the Thiessen polygons for a collection of point features we need to find bisecting lines, which are geodesics (they are straight); but for a collection of other kinds of features, such as points and segments, the boundaries of the Thiessen polygons include portions of parabolas (in the plane). Maybe you don't want to support this...
Set-theoretic overlays (intersection, union, difference, complement). These operations do not create any new kinds of curves.
Parallel translation and rotation. These are usually not possible to perform exactly on an ellipsoid (because it is not a homogeneous space), but are straightforward on the sphere. On the sphere, these operations do not create new kinds of curves.
The really problematic class of curves you propose consists of the general rhumb lines (loxodromes). Lines of latitude are rhumb lines but (on the sphere at least) they are also circles, so they present no additional problem. But general rhumb lines are complicated beasts: if they are not meridians or parallels, they spiral into one pole or the other. Buffers and parallel translations of rhumb lines will be genuinely new types of curves. You would have to represent these results as broken segments of lines and circles, which would defeat your purpose (and be fairly difficult to compute). Therefore I suggest not trying to support rhumb lines exactly.
In sum, it looks like you can be successful in your program if (a) you work on a spherical model of the earth rather than the more general ellipsoidal ("spheroidal") model and (b) you limit certain constructions such as Thiessen polygons (and medial axes, which are closely related) to collections of points.