I can speak to Ivan the Terrible, at least, but there are a handful of ways to gain these titles. Epithets either arise during the ruler's lifetime (as is the case with Peter the Great, as following the Great Northern War the noble Gavriil Golovkin pronounced him 'the Great') or after their death, based on reflection of their actions or a loosening of censorship.

Ivan the Terrible was the first Tsar of Russia and, despite unification and reforms, is regarded poorly for (among other reasons)

i) Losing wars. Ivan did win some wars, certainly, but they were not substantial or immediately beneficial for Moscow. The rather minor first Russo-Turkish War was not of great benefit for Russia, and economically the Ottomans were guaranteed safe trade routes. After bouncing back and forth Ivan retook the former Kazan Khanate, which had been unstable for some time. He ultimately failed to keep a stable border here. [1]

The Livonian War, which he conceded just a year before his death, was incredibly devastating for Russia.

ii) Poor domestic leadership. The so-called Izbrannaya Rada that gave Ivan the title of Tsar made rather poor decisions, followed by Ivan's own mismanagement; the Moscow Uprising, precipitated by drought, famine, and fire, resulted in tightening restrictions and the consolidation of power at the expense of Muscovite citizens [2]. After Ivan rejected the council we get the Livonian War, a protracted boondoggle that resulted in Russia losing significant Baltic territory to pretty much every regional state. In the middle of this war Ivan ordered Novgorod, at the time a significant city, raided and burned by the oprichniki due to a putative rebellion. Further Crimean wars resulted in the burning of Moscow in 1571 which led to more unrest. The oprichniki were state police that were not particularly competent, but balanced their incompetence with brutality. All of this was financed by increasing taxation, another unpopular move.

iii) Unstable borders. By the 1570s Ivan had lost some of the lands he had retaken, including Astrakhan. Attempts to expand control in Crimea and Siberia went poorly, which in conjunction with westward failures in Livonia both weakened Russian control of fringes and gave the very public impression of an unstable state. [1]

As an aside, Ivan's personal life didn't help; he is reputed to have murdered his son Ivan, resulting in his much-less-competent heir Feodor taking the throne and the dissolution of the Rurikid dynasty. [see Repin's painting]

So in his lifetime, Ivan was very unpopular, at one point stepping down from the title. Early histories of his reign attest to his unpopularity [3,4].

When it comes his epithet, 'the Terrible' is not ascribed until the historian Vasiliy Tatishchev, in the mid-18th century (published posthumously). Ivan IV was a designation of Karamzin, starting now with the Muscovite Grand Prince Ivan Kalita, or 'Ivan The Money-Purse [Holder],' following Tatishchev. Karamzin harshly critiqued the latter half of his rule, but noted the early successes of unification. The various impressions of 'Ivan the Terrible' crystallize in the mid-19th century with Lermontov's poem "The Song of the Merchant Kalashnikov," though the Tsar does show leniency to some degree, and paintins by Ilya Repin and Konstantin Makovsky, and a play by Alexei Tolstoy. Tolstoy's characterization of Ivan is based on Karamzin's, and is a very interesting look at Ivan's ambitions; he also writes a novel entitled 'The Silver Prince' on the same subject.

Another consideration is the translation. Иван Грозный, 'Ivan the Terrible,' can be translated as 'fearsome' - Grozny is the capital of Chechnya, for example, and doesn't strictly mean 'Terrible.'

If you are interested in Ivan's rule in particular, Isabel de Madariaga has an excellent book on his reign, Ivan the Terrible. Karamzin's History of the Russian State gives a very nice view of the early-19th century interpretation of pre-Romanov Russian history. The writings of Jerome Horsey are also worth taking a look at to see early European-Russian relations.

References:

[1] De Madariaga, Isabel. Ivan the Terrible. Yale University Press, 2005.

[2] The exact place of this council is unclear; see, e.g., Filyushkin, История одной мистификации: Иван Грозный и "Избранная Рада"

[3] Fennell, John Lister Illingworth, ed. Prince AM Kurbsky's history of Ivan IV. Cambridge University Press, 2008.

[4] Pennington, Anne Elizabeth. "A Sixteenth-Century English Slavist." The Modern Language Review (1967): 680-686.