Caesar in Asia
After Sulla pardoned Caesar, he still thought it a wise idea to avoid potentially falling back into disfavor. Caesar, at 20 years old, left Rome for Asia in 80 BC. He next joined the staff of the Asian governor, Praetor Marcus Minucius Thermus, and got an advance start on his military and political career.
While in service to Thermus, he was sent on a diplomatic mission to King Nicomedes IV of Bithynia with the purpose of raising a fleet. Caesar seems to have stayed so long in Bithynia that rumors began to circulate about what he was doing. By the time he did return to Thermus, with the fleet he was sent to muster, it was widely believed that Caesar was having an affair with Nicomedes. His fast return to Bithynia, to settle some affairs for the King, added to the gossip.
The incident (there is no evidence other than speculation) was a great source of joy to Caesar's enemies later. They delighted in referring to him as the Queen of Bithynia.
As he struggled for the rest of his life to quell the rumor, he turned into a notorious seducer of Roman women. Possibly, a designed effort in part to refute the charges, Caesar would later have affairs with countless Roman noblewomen. Wives and family of Senators were his favorite targets, and though he was never quite able to live down the Nicomedes rumor, he assuredly had an overwhelming reputation as a ladies man.
On another personal issue, it's important to note Caesar's apparent epilepsy. While his case must certainly have been mild, as it would've been difficult to achieve all that he did while undergoing chronic seizures, there is little question that he had some sort of affliction causing occasional loss of bodily control or mental lapses. In the ancient world, without medicines or treatments of any sort, a debilitating condition such as that, in severe form, would certainly have precluded Caesar from many of his accomplishments.
There was a definite stigma attached to the disease, where people believed it was a direct affliction of the gods, and the moon in particular. To overcome social stigmas, if it became common knowledge, would have been difficult at best, but still the brilliant politician may have used it to his advantage. While there is no direct evidence to suggest this, it shouldn't be put past the mind of Caesar to use epilepsy as proof of his direct relation to Venus. In so doing, he could use an apparent weakness to spread his fame and dignitas by proving his divine favor on earth.
Military Operations in Asia
After the incident with Nicomedes, Caesar returned to Asia, and was involved in several military operations. In 80 BC while still serving under Thermus, he played a pivotal role in the siege of Miletus. During the course of the battle, Caesar showed such personal bravery in saving the lives of legionaries that he was later awarded the corona civica (oak crown). The award was of the highest honor, and when worn in the presence of the Senate, they were forced to stand and applaud his presence. Caesar wore the crown whenever it was opportune, as he certainly delighted in 'rubbing it in' to his enemies.
Caesar next served under Servilius Isauricus in Cilicia but only for a short time. Hearing of Sulla's death in the same year, it was finally safe to return to Rome. For the next few years, he worked diligently at his oration skills by serving as a trial attorney, in which he excelled. In just his early twenties, he was gaining a powerful reputation for a populares champion, taking on several elite aristrocrats.
Caesar as an Attorney of Law
Of the most notable, in 77 BC, Caesar brilliantly prosecuted the ex-Consul Gnaeus Cornelius Dollabella for extortion from various Greek cities during a term as governor. Though the end result was a victory for Dolabella, his reputation was terribly damaged. The great orator Cicero even commented, "does anyone have the ability to speak better than Caesar."
Another high profile, though ultimately unsuccessful, prosecution of Gaius Antonius Hybrida followed. Only the bribery of the Tribune of the Plebs bought Hybrida an acquittal, but Caesar's star was rising fast. With such a promising career well under way, Caesar next sought to continue his education in rhetoric and oration; key skills for any Roman politician.
Caesar and the Cilician Pirates
An education begun under the same teacher as Cicero - Marcus Antonius Gnipho - needed further refinement. In 75 BC, Caesar left Rome to study in Rhodes under the great teacher Apollonius Molon.
While en route, however, he was waylaid by Cilician pirates and taken hostage. A Roman patrician was a good prize to catch and the pirates demanded 20 talents (nearly 5,000 gold coins) for his release. Caesar, showing his arrogance, mocked the pirates by insisting that a rising patrician such as himself was worth no less than 50 talents (12,000 gold coins).
In all he was held for 38 days and used the time to write speeches and practice his rhetoric on his captors. Though apparently treated quite well, Caesar vowed, and told them often, that when he was released he would come back to capture and crucify the lot of them.
After his release, he did just that, mustering his own small fleet to accomplish the task. Good to his word, the pirates were hunted down and crucified. Though as a sign of his apparent aversion to cruelty, it's been suggested that the men were killed quickly to prevent the horrible death of crucifixion.
Defending Roman Asia
Prior to his return to Rome, Caesar served again in military service to Rome. As Mithridates of Pontus invaded Roman Asia, Caesar jumped at the chance for further military glory. He took it upon himself to raise a small army of provincials and gathered enough strength to defend several small towns.
Though technically illegal to lead a military operation without Senatorial commission, both cases were likely ignored because of the service he provided to the state.
Caesar then returned to Rhodes very briefly until the death of his cousin Gaius Aurelius Cotta. Caesar was appointed to replace Cotta as a Pontif (priest), and by 73 BC, he was well educated in the political as well as military arts.
Now 27 years old, he began the voyage back to Rome to begin his climb up the Roman political ladder.