Caesar was never tribune (nor was he eligible to be), unless you mean his time as military tribune immediately after his return to the city--the tribunes of the plebs and the military tribunes are two completely different offices. Caesar's career in advocacy mainly occurred before he left the city to study with Apollonius at Rhodes. I've written a little bit on Caesar's legal career here--most politically-inclined Roman men entered a career of public advocacy before they ran for office, and Caesar was no different, though the chronology of his career was made a bit funky by his two sojourns in Asia. Caesar was particularly famous for two brilliant prosecutions, against Dolabella in 77 and against Publius Antonius--I speak about these prosecutions in the thread I've linked already. In both cases his prosecution was considered brilliant, although both he lost. Suetonius says that he fled to Rhodes to escape the hatred that he had incurred among many of Dolabella's supporters in the senate, and Plutarch says that his prosecution of Publius Antonius was so effective that Antonius only escaped by appealing to the tribunes in the city, claiming that he could not as a Roman citizen be given a fair trial in Greece among Greeks (he was tried before Lucullus, the praetorian governor of Macedonia). The trial of Antonius was particularly popular, as Caesar had undertaken it at the behest of the provincials, much like Cicero's prosecution of Verres on behalf of the Sicilians.

It is said he was an extremely eloquent man. How truthful is this statement?

Cicero rated him quite highly as an orator. Suetonius reports that he said of Caesar, in a letter to Cornelius Nepos:

quid? oratorem quem huic antepones eorum, qui nihil aliud egerunt? quis sententiis aut acutior aut crebrior? quis verbis aut ornatior aut elegantior?

What? Who would you place before him as an orator, of those who do nothing else? Who is more passionate [literally pointed, acute, sharp] or more abounding in his sayings [sententia is a funny little word, it means both sayings in the literary way (like, phrases, aphorisms, epigrams, that sort of thing) but it also means the official statement and opinion on a subject given by a politician]? Who is more elegant or more handsome with his language?

Awfully high praise, coming from the man that every Roman of the day would admit readily was the greatest living orator. Cicero himself says in the Brutus (which is quoted by Suetonius but which survives in the original as well):

Caesar autem rationem adhibens consuetudinem vitiosam et corruptam pura et incorrupta consuetudine emendat. itaque cum ad hanc elegantiam verborum Latinorum—quae, etiam si orator non sis et sis ingenuus civis Romanus, tamen necessaria est—adiungit illa oratoria ornamenta dicendi, tum videtur tamquam tabulas bene pictas conlocare in bono lumine. hanc cum habeat praecipuam laudem in communibus, non video cui debeat cedere. splendidam quandam minimeque veteratoriam rationem dicendi tenet, voce motu forma etiam magnificam et generosam quodam modo.

But Caesar, holding to his principle [ratio here means something like "literary theory," or perhaps "manner of speech"], improves a faulty and corrupt habit [of speaking] with a pure and uncorrupted one. And so, he joins to the elegance of Latin speech--which, even if you are not an orator and were born a native Roman citizen is still necessary--the orational splendor of speaking, and then he seems as if he presents well-painted paintings in the best light. Since he has this particular praise in the commonness of his speech [that is, he does not use bombastic Asiatic language and does not invent ridiculous words like Sisenna, whom Cicero has just spoken about, does] I do not see to whom he should yield the palm. And he holds the same splendid manner of speaking without craftiness, beautiful in gesture and voice, and in the same way there it is even magnificent and noble

Praise doesn't get much higher than that, although Cicero goes on to say that Caesar's written works are just as brilliant, and has Brutus' character admit that he's quite taken by Caesar's prose. Caesar was something of an authority on prose, the author of a two-book treatise de analogia "on analogy," explaining the use of analogy in rhetoric. He also wrote a series of speeches called the Anticatones, "the speeches against Cato"--these two works Suetonius says he wrote while travelling, the former across the Alps to Cisalpine Gaul and the latter on his way to Munda (he seems to have written in what free time was available to him, as a sort of hobby). His letters and speeches were widely published and Suetonius holds them in high regard--we have some of his letters to Cicero, although the ones we have tend to be rather short and hurried. He also wrote in his youth a collection of sayings, dicta collectanea, which Augustus refused to allow Macer to publish. This is only his prose, besides the de Bello Gallico and the de Bello Civili--Caesar also wrote a rather large amount of poetry, which received mixed reviews in antiquity, though Suetonius seems to praise it. Nor should the de Bello Gallico and the de Bello Civili be discounted as rhetorical pieces of prose simply because they're easy enough for advanced high school students to make sense of. Cicero in the Brutus considers them to be masterworks, and their style certainly made quite a splash--Caesar was the authority on the Direct Style. You'll notice that Cicero also praised his diction and gestures, which Suetonius does as well:

Pronuntiasse autem dicitur voce acuta, ardenti motu gestuque, non sine venustate.

And he is said to have spoken with an impassioned [again, acutus literally means "sharp"--Suetonius might be saying that Caesar's voice is high-pitched, a possible translation of the word, but the emphasis is that his speech was passionate] and with passionate [ardeo literally means "to burn," and can be used metaphorically the same way we say "inflamed"] motions and gestures, which were not without elegance.

As a sort of closing remark, Caesar's speech against Cicero's decision to execute the Catilinarians without trial is a perfect example of his abilities as an orator. It survives only in Sallusts' transcription, which is certainly largely fabricated, although it's possible, perhaps even probable, that much of the actual content is from Caesar, though the wording is all Sallust. Suetonius for example seems to back up the basic subject matter of Sallust's speech. His speech was so moving and so persuasive that the senate almost relented. Plutarch reports that:

οὕτω δὲ τῆς γνώμης φιλανθρώπου φανείσης καὶ τοῦ λόγου δυνατῶς ἐπ᾽ αὐτῇ ῥηθέντος οὕ μόνον οἱ μετὰ τοῦτον ἀνιστάμενοι προσετίθεντο, πολλοὶ δὲ καὶ τῶν πρὸ αὐτοῦ τὰς εἰρημένας γνώμας ἀπειπάμενοι πρὸς τὴν ἐκείνου μετέστησαν, ἕως ἐπὶ Κάτωνα τὸ πρᾶγμα καὶ Κάτλον περιῆλθε

But thus, with his opinion [sententia, in the meaning I gave above as the official opinion of a Roman politician] seeming so humane, and the speech delivered to the senate so powerfully, not only did those rising to speak after him agree, but even those who had spoken before him renounced the opinions they had put forth and changed their opinions to his, until the matter came around to Cato and Catulus [to speak]

At which point Cato basically said, "nah don't listen to him, you don't like him, kill 'em all!" In any case, Caesar's speech was one that was probably largely improvised, since Cicero had not made it clear what his intentions towards the Catilinarians were until that very moment. If that's not an impressive piece of oratory I don't know what is