An Ally is:
a friendly creature willing to risk themselves for your mutual goal
As Carcer states, the term "ally" is not explicitly defined within the rules. However, that does not mean we have to immediately jump to the normal English meaning of the word when there are other options of higher relevance1. We can instead search for use of the word within the core rules and see if any context patterns emerge. In this case, there are so many uses of the word in other abilities that we can say with reasonable confidence what it means.
Being an ally is closely linked to being friendly
In contrast to being an "ally", being "friendly" is explicitly defined within the rules. The PHB tells us what being friendly means (p. 185):
In general terms, an NPC’s attitude toward you is described as friendly, indifferent, or hostile. Friendly NPCs are predisposed to help you, and hostile ones are inclined to get in your way
And the DMG adds to this understanding (p. 244):
A friendly creature wants to help the adventurers and wishes for them to succeed. For tasks or actions that require no particular risk, effort, or cost, friendly creatures usually help without question. If an element of personal risk is involved, a successful Charisma check might be required to convince a friendly creature to take that risk.
So by definition, a friendly creature wants you to succeed, but is not always willing to risk itself to help you. Since we have a good definition of what 'friendly' means, we can now note that about a third of the time when the PHB mentions allies, it also mentions them as being friendly. Clearly the two terms are related:
PHB, Help Action, emphases mine:
Alternatively, you can aid a friendly creature in attacking a creature within 5 feet of you. You feint, distract the target, or in some other way team up to make your ally's attack more effective. If your ally attacks the target before your next turn, the first attack roll is made with advantage.
PHB, Forest Gnome (p. 37), emphases mine:
Forest gnomes tend to be friendly with other good-spirited woodland folk, and they regard elves and good fey as their most important allies. These gnomes also befriend small forest animals and rely on them for information about threats that might prowl their lands.
Similar links between 'friendly' and 'allied' can be found in the descriptions of Character Building (Building Bruenor, Step 4), the Tiefling Race details, and the Bard Class Feature, Song of Rest
Thus it is clear that being an ally is linked to being friendly.
However, there are other places in the PHB where being an ally is mentioned without an explicit mention of friendliness. We can look to these to see whether it is ever possible to be an ally without being friendly. A review of who a Bard inspires (p. 54, in two places), the functions of the Cleric class (p.56), who can benefit from a Battlemaster's Distracting Strike (p.84), who a Ranger can teach (p.90), who can benefit from a Wizard's Illusory Realty (p. 118), who a flawed Folk Hero has trouble trusting (p.132), who might be healed with the Healer feat (p. 167), and who can be targeted with an Aid spell (p.211) finds that in no case is it suggested that an ally would not be friendly.
It appears that allies are always friendly. If so, what then is the difference between an ally and a friend? Here we can return to the DMG definition of friendly, and note that while a friendly creature always wants its friends to succeed, it is not always willing to risk itself to help. So one possible definition of ally would be that while a friendly creature wants you to succeed, an ally is a friendly creature that is furthermore willing to incur risk, effort, or cost to itself in order to help you succeed.
This proposed definition, that an ally is willing to incur personal risk on your behalf, is consistent with all the uses of 'ally' in the PHB. It is especially congruent with the definition of the Help action, where you must place yourself within five feet of a foe to give your ally advantage. It makes sense with the feature Pack Tactics (found in the PHB descriptions of Dire Wolves, Lions, Reef Sharks, and Wolves), which confers advantage on your attacks when an ally of yours is willing to risk themselves by being adjacent to your shared foe. And it even touches on the distinction made in the description of Forest Gnomes, where small woodland creatures are just friends, but more combat-ready fey and elves are not only friends but allies as well.
Being an ally means being willing to incur risk on someone's behalf
If we accept this as a definition, then ruling on whether a particular creature counts as an ally for a particular feature comes down to their willingness to accept risk on your behalf (or vice versa).
In the complicated circumstances suggested by the original question (a doppelganger, a spy, an unrequited love) the DM can rule about the sincerity of their feeling, or the PC's feeling, even if it is misplaced or mistaken.
The source of a Paladin's power is their Oath - their deep personal commitment to their values. Like their spells, the Exalted Champion ability is a function of the paladin's belief.
Your allies have advantage on death saving throws while within 30 feet of you.
You have advantage on Wisdom saving throws, as do your allies within 30 feet of you.
Who does the paladin consider their ally? Who are they willing to risk themselves for? It might be a mistake for the paladin to risk themselves on behalf of the doppelganger or the BBEG, but if they are willing to do so, and if doing so advances their mutual goal, then those individuals are indeed allies, at least within the context of a specific encounter. Likewise, in their fight against a spy who is an unrecognized compatriot, the paladin would not be willing to risk themselves on behalf of someone they believe to be their foe. The spy would gain no advantage from exalted champion so long as the paladin did not believe it should extend it to them2.
Purple Dragon Knights (or, outside the Forgotten Realms, bannerets) are not paladins. Rather, they are Fighter class characters, often with high charismas. A knight "inspires greatness in others by committing brave deeds in battle." Thus, while a paladin's abilities are powered by their own Oath, a Purple Dragon Knight's abilities arise from the reactions of others that see them. As such, the belief of the observer is as important as the belief of the Knight. In order for a creature to benefit from a Knight's ability, it must be sincerely inspired. Thus, a DM could rule that a doppelganger or a BBEG would not benefit from the Knight's ability, while their unrecognized friend would. This distinction can even be seen in the specific wording of the ability:
Starting at 10th level, when you use your Action Surge feature, you can choose one creature within 60 feet of you that is allied with you. That creature can make one melee or ranged weapon attack with its reaction, provided that it can see or hear you.
Notice that the Exalted Champion benefits the allies of the paladin, those whom the paladin considers allies (regardless of how they feel about the paladin). The Inspired Surge, however, benefits those that are allied with the Knight, that is, those who consider themselves allies of the Knight. The Knight still must choose the creature, but unless the Knight's feelings are reciprocated, the ability as written shouldn't work.
1Personally, I try to work within the following hierarchical framework when interpreting a word: (1) Is it a game term? If not, (2) Are there multiple, consistent context clues from its use in core books or official rulings? If not, (3) can designer intent be inferred through unofficial statements? If not, (4) what normal English meaning seems closest to the way it is used within the rules?
2As a divine caster, there is also fertile ground for a DM to subvert this ruling if the paladin has a god as well as an Oath. If the doppelganger does not get advantage on their Wisdom save but the disguised spy does, the paladin would do well to ask themselves, 'what is my God trying to tell me here?'