What you are noting is that the definition of "sane" (also "intelligent", "athletic", "reasonable", etc.) are not so much defined recursively as they are questions of social comparisons of behaviour.
Some of these are defined in terms of being similar to a perceived norm (where 'norm' is interpreted in a vaguely statistical sense, i.e. what one can expect on average) without too much variation from it; others are defined in terms of some single dimension of ordered comparison, in which one substantially exceeds the norm. Sanity would consist of similarity to average behaviour in certain respects, and in particular denotes some sort of standard of predictability. "Mad", being the opposite of "sane", would naturally represent behaviour which is at substantial variance from the norm; especially if it is a mode of behaviour which is potentially dangerous to themself or others.
Dalí's ironic quote (in which he implies that he is not mad by virtue of believing that he is mad) points out one common idea of madness; that someone whose behaviour is very much at odds with what is normal, and who is not aware of this deviation (or who claims superiority from this deviation according to an obscure code of ethics), is that much harder to predict and therefore possibly dangerous to be around; whereas someone like Dalí, who is very self-conscious of his deviation from the norm, behaves in a way which is unusual but (because he is conscious of his behaviour and his role in society) is not dangerous.
(Note also that dangerousness alone is not sufficient to define madness. In many countries, police are often dangerous people — but only under certain circumstances, and usually you can expect any given officer to be dangerous under those same circumstances. For instance, if you kill another police officer, you can expect to be in mortal peril. The circumstances under which you are in danger of police action will vary from location to location, but within a location there is usually some roughly-understood range of behaviour that can be expected of the police. Therefore, people will rarely be inclined to describe the entire police force as 'mad' on the basis of their potential dangerousness.)
Your example of omnipotence is not so much a matter of recursive definition as it is an example of a precise definition in a domain of discourse where the notion of possible actions or properties of objects is impredicative, as in naïve set theory. The real question for omnipotence is what other properties of objects are well-formed and admit discussion as the subject of the actions of an omnipotent creature. For instance, consider a creator who made an 'immovable' rock: is 'immovability' a property an object can have in itself, when motion is described relative to some frame of reference? Furthermore, if you resolved that puzzle and then the creator then moved that rock, wouldn't this be tantamount to first removing the rock's property of immovability (which surely an omnipotent being could do) and then moving it? Perhaps the crux is whether an omnipotent creator could make a rock that she could not unmake — but is 'unmakability' a property of the object? What we're noticing here is that what omnipotence means depends on the other properties which lie in the domain of discourse; this doesn't make it recursively defined, but whether or not it is logically consistent depends on what properties you suppose are logically coherent in the universe that the omnipotent being inhabits, in the same way that the notion of an "odd number" (and the associations normally made to it) much more sense in the integers than in the real numbers.
