В словарях идиому at (your) earliest convenience принято переводить как «при первом удобном случае» или «как только вы сможете». К примерам употребления в речи можно отнести фразы типа:
I will call you back at my earliest convenience.
If you want to get ahead of the game, take this pro tip and complete the task at your earliest convenience.
He will return the borrowed book at his earliest convenience.
Как вы видите, это самое convenience может принадлежать кому угодно в зависимости от контекста.
Первым (или одним из первых) упоминанием идиомы at (your) earliest convenience на письме некоторые считают фразу Please, at earliest convenience send me the name of the vessel…, которая появилась в периодическом журнале The Lower Canada Jurist в не таком уж далёком 1860 году.
Выражение это, как вы догадываетесь, носит весьма формальный характер, поэтому чаще всего используется в деловой переписке или беседе. Разумеется, им не стоит отвечать, когда вас попросили что-то сделать as soon as possible, поскольку в таком контексте она прозвучит неуважительно к собеседнику. Хотя as soon as possible само по себе можно считать одним из её синонимов. К которым принято относить такие сочетания как:
At the earliest opportunity
Without delay
As soon as you can
At the soonest possible time
As promptly as possible
At the first chance
As quickly as you can
When you have a moment