Difference between Russian/Lithuanian "Grand Duke" and Western "King" is rather semantic only.

Russian and Lithuanian words for duke are "knyaz" (Князь) and "kunigaikštis" (older form- "kunigas") respectively. As you can clearly see they are cognates with Germanic "king"' "könig", "konge" and so on.

However, in Western Europe and Scandinavia, realms formed by removing kings/königs until there was only one left: dozen of Anglo-Saxon kingdoms were forged in Heptarchy and eventually Wessex absorbed them all by one mean or another replacing, for example, Kingdom of East Anglia with Jarldom of East Anglia. Similar thing happened in Scandinavia- sagas names an insane amount of petty kingdoms and kings, but in historical times we see only three remaining.

In Rus, no one seemed to be concerned about removing knyazes, quite contrary in fact. Due to size of the country, ruler was unable to keep as close control over remote parts of the realm as English kings could, thus local rulers remained semi-independent, with head of the Rurikovich clan keeping the title of the overlord- "Grand Duke" could be more precisely translated as "Chief Duke". Due to the lack of clear rules of inheritance, Rurikovich's soon broke up in to number of smaller clans that completed among and inside themselves, while with every new generation new and new duchies sprang up. Russian term for them is udel, partial duchy ((уде́л) Уде́льное кня́жество), as every member of ruling dynasty was entitled to the share (part) of inheritance. (Moscow for example. It was a border fortress of the Vladimir-Suzdal until it was given to the youngest son of Alexander Nevski and thus become duchy in it's own right). And as of early 12th century title itself was pretty much an empty honor, conventions remained.

To say it shortly, in Western Europe, petty realms were united in to the large states and meaning of the title "king" evolved from "tribal leader" to the "monarch of the state", while Kievan Rus disintegrated an such evolution simply never happened. So then Russia finally was united, Ivan IV choose an imported title of Caesar (Tsar) to signify his new position.

Lithuanians went a middle road- the "Grand Duke" is taken from Rus and in Ruthenian lands of the GDL old Kievan Rus system was fallowed-Polock, Kiev and so on remained largely autonomous duchies, with Gediminid installed as a duke (at least in more important ones. In many smaller duchies various branches of Rurikovich remained). However in Lithuania propria we know many dukes from the times of Mindaugas, but by the end of 14th century only three families beside Gediminids themselves had the title, so clearly there was an effort of centralization.

And Lithuania was a Kingdom for 1251-63 but otherwise was only a Grand Duchy from then until the 19th century. Yet it owed fealty to no King. Why then was its ruler not considered the equal of its neighboring Kings?

Short answer- because of the bad timing. England, Scotland, Denmark etc.were formed as realms in late dark ages, so to be recognized as the kingdoms they had to be simply Christian and independent. Lithuanian state come to be only in 13th century and by then, authorization by Pope (or at least emperor of HRE) was necessary for recognition of new Christian kingdom. Mindaugas managed to secure papal support, but after his murder in 1263, Lithuania reverted in to paganism and status of kingdom was lost. And Mindaugas kingdom was the last new kingdom in Europe- no new kingdoms were created after that up until 1701. That does not mean Gediminid did not tried to gain royal crown and eventually they did- in 1386 Grand Duke Jogaila become King Wladyslaw II of Poland. He moved to Poland and took title of Supreme Duke of Lithuania. Kings of Poland used this title since then to signify suzerainty over Lithuania. Lithuanian nobility fiercely defended they independence but Lithuania's status as of junior partner was irrevocably established. But until 1386, Lithuanian rulers were often refereed as kings (in Wigand's of Marburg Chronica nova Prutenica for example).

(This is very, very, very abridged version, but I hope it gives you a general idea).

So basically this King- Grand Duke distinction much depends on the shift in the meaning of the word- "king" in Heimskringla is rather the same thing as "knyaz" or "kunigaikštis" and in middle ages difference between "king' and "grand duke" was just differences of nomenclature in different languages (Grand duke Algirdas translated his title as magnus rex in his Latin correspondence), but as political system evolved, that grew in to actual differences in hierarchy then Poland-Lithuania union was formed.