There are two ways to answer this: the reputation according to the highly-romanticised ROTK, and the historical person. According to fiction, he is completely without achievement yet his greatness speaks for itself once you meet him. In reality, he was a highly intelligent, well-connected, but inexperienced young man, with the reputation to match, i.e. not much.
ROTK
It is true that before serving Liu Bei, Zhuge Liang was completely inexperienced, at least as a strategist. Actually, the novel deliberately leaves the question of how he earned his reputation unanswered. His reputation, at least to Liu, stemmed solely from recommendation from very wise and talented men: Sima Hui, Xu Shu and other peers, all who insisted that Zhuge was even greater than they. You, like Liu, are meant to see Zhuge as a great mystery, and be intrigued: just who is this man, who has no accomplishments at all, and yet is highly regarded by none other than Xu Shu, the man who read Cao Ren like a book?
The novel teases at all this during the three visits to the thatched cottage sequence, one of the best written parts and the midpoint of the Liu Bei arc. Here the mystery and intrigue gets whipped up into a frenzy:
Sima Hui tells how Zhuge believes that Xu Shu and his friends may be capable enough to become commandery administrators, but he is as capable as Guan Zhong and Yue Yi. Guan Yu is incredulous, but Sima believes that Zhuge is even greater, comparable to Jiang Ziya and Zhang Liang. Those two men are widely considered among the greatest strategists in Chinese history, comparable to Alexander the Great or Hannibal.
時雲長在側曰：「某聞管仲、樂毅，乃春秋戰國名人，功蓋寰宇。孔明自比此二人，毋乃太過？」徽笑曰：「以吾觀之，不當比此二人。我欲另以二人比之。」雲長問那二人。徽曰：「可比興周八百年之姜子牙，旺漢四百年之張子房也。」
On their first trip, the three brothers encounter simple farmers singing something composed by Zhuge, whose short lyrics basically described the meaning of life. This establishes him as a philosopher of incomparable wisdom.
次日，玄德同關、張并從人等來隆中，遙望山畔數人，荷鋤耕於田間，而作歌曰：
蒼天如圓蓋，陸地似棋局。
世人黑白分，往來爭榮辱。
榮者自安安，辱者定碌碌。
南陽有隱居，高眠臥不足。
When they reach his residence, it is described as having the serenity of heaven on earth.
不數里，遙望臥龍岡，果然清景異常。
During the trips, Liu repeatedly encounters people - friends, family of Zhuge - singing or reciting poems of great wisdom and insight, and he mistakes them all for Zhuge at first. Zhuge is so awesome that anyone related to him becomes wise also.
When they finally catch Zhuge present, he is sleeping. When he finally wakes, he composes a poem on the spot. He's just that good.
又立了一個時辰，孔明纔醒，口吟詩曰：
大夢誰先覺？
平生我自知。
草堂春睡足，
窗外日遲遲。
Later when Zhuge presents his Longzhong Plan, his reputation is sealed. We, like Liu, are completely certain that Zhuge is the bee's knees. Bowang was just a demonstration to convince dunces like Guan and Zhang.
In Reality
Zhuge had powerful connections and wasn't some outsider as the novel depicts. However his own reputation wasn't that great; only his closest friends recognised his talent.
According to his biography in Records of the Three Kingdoms, he was self-confident, and compared himself to Guan Zhong and Yue Yi, but this opinion was not widely shared. In fact, only his friends (such as Xu Shu) agreed.
每自比於管仲、樂毅，時人莫之許也。惟博陵崔州平、潁川徐庶元直與亮友善，謂為信然。
Despite his then-current occupation as farmer, he was well-connected and was previously being groomed to a life as public official. Unlike the novel which depicts him as a near-mythical hermit-farmer unknown to the outside world, he would have been well-known at least among the Jing Province gentry. He comes from a family of public officials: one of his ancestors was a Colonel Director of Retainers 漢司隸校尉諸葛豐後也。. His father was vice-administrator of a commandery 父圭，字君貢，漢末為太山郡丞。. His brother Zhuge Jin was already a high-ranking and trusted official within the Wu court.
He's also related to Liu Biao by marriage. It's a bit indirect though, and it goes like this: his father in law, Huang Chengyan, married the elder daughter of Cai Feng, who also had a son (the influential general Cai Mao) and a daughter who married Liu Biao (Lady Cai). Zhuge can call Liu Biao "uncle in law".
His uncle/foster father was quite well connected: he was a direct subordinate to Liu Biao 玄素與荊州牧劉表有舊，往依之。; he was a commandery administrator under Yuan Shu, and even managed to get Zhuge a (minor) official position 從父玄為袁術所署豫章太守，玄將亮及亮弟均之官.
Why would Liu personally visit Zhuge?
This leaves very interesting questions about the three visits. Given Zhuge's reputation, which wasn't that great, why would a famous warlord like Liu personally attempt to visit him in a remote village, thrice?
Here the historical records contradict. Both Records of the Three Kingdoms, the most reliable, and (the first) Chu Shi Biao, authored by Zhuge himself, say that the three visits did happen. However according to Brief Account of Wei and Jiuzhou Chunqiu, it was the other way around: Zhuge visited Liu.
According to this interesting account, Zhuge visited Liu but was ignored due to his youth. When all the other guests left, Zhuge talked to Liu and presented a plan to conscript and tax the unregistered war refugees. This greatly impressed Liu and Zhuge was treated as an honoured guest.
亮乃北行見備，備與亮非舊，又以其年少，以諸生意待之。坐集既畢，眾賓皆去，而亮獨留，備亦不問其所欲言。備性好結毦，時適有人以髦牛尾與備者，備因手自結之。亮乃進曰：「明將軍當復有遠志，但結毦而已邪！」備知亮非常人也，乃投毦而答曰：「是何言與！我聊以忘憂耳。」亮遂言曰：「將軍度劉鎮南孰與曹公邪？」備曰：「不及。」亮又曰：「將軍自度何如也？」備曰：「亦不如。」曰：「今皆不及，而將軍之眾不過數千人，以此待敵，得無非計乎！」備曰：「我亦愁之，當若之何？」亮曰：「今荊州非少人也，而著籍者寡，平居發調，則人心不悅；可語鎮南，令國中凡有游戶，皆使自實，因錄以益眾可也。」備從其計，故眾遂強。備由此知亮有英略，乃以上客禮之。
There's a minority opinion that this account is truthful, and the three visits didn't happen. There's another, purely conjectural opinion that both are truthful; perhaps Zhuge visited Liu first, earned his trust, then Liu later visited Zhuge where they discussed the Longzhong Plan.
The mainstream opinion is that Records and Chu Shi Biao are reliable. But there is doubt as to exactly how the three visits worked out. Records is extremely brief: "[Liu] visited thrice, and met [with Zhuge]." 凡三往，乃見。 Chu Shi Biao is a bit more detailed: "[Liu] lowered himself and visited me thrice in the thatched cottage, where he consulted me on the affairs of our time." 先帝不以臣卑鄙，猥自枉屈，三顧臣於草廬之中，諮臣以當世之事 The way Chu Shi Biao depicts it suggests an alternate version of the three visits: Liu visited and met Zhuge thrice. This is more believable, as visiting thrice but only meeting on the third occasion would have required uncommon patience (or desperation) on Liu's part. The way Records is written, it could be interpreted either way. One other thing: thrice in classical Chinese also has the meaning of many times. That is, Liu visited Zhuge repeatedly, over a long time span, where they slowly built up trust in each other, and formed the Longzhong Plan. This version is much more plausible than the novel's, where Zhuge presents the very detailed Longzhong Plan on his first meeting with Liu.
But let's say we take the mainstream position that it was Liu who first visited Zhuge, and whatever happened - whether Liu visited thrice, or many times, and whether he met Zhuge on all occasions or only after three visits - we still need to explain why Liu would bother with the first visit. Why didn't he summon for Zhuge, and why would someone of Liu's stature personally visit Zhuge, someone with very little renown? Was Liu just a really humble guy, as Zhuge writes in Chu Shi Biao?
Zhuge was highly recommended by Xu Shu and Sima Hui. This part of the novel is true. According to Xiangyang Ji, Sima Hui singled out Zhuge and Pang Tong as the two advisors to recruit from the region, describing them as crouching dragon and young phoenix respectively.
德操曰：「儒生俗士，豈識時務？識時務者在乎俊傑。此間自有伏龍、鳳雛。」備問為誰，曰：「諸葛孔明、龐士元也。」
According to Records, Xu Shu was already highly trusted by Liu, and not only recommended Zhuge, calling him a crouching dragon, but said that Liu should personally visit him.
徐庶見先主，先主器之，謂先主曰：「諸葛孔明者，臥龍也，將軍豈願見之乎？」先主曰：「君與俱來。」庶曰：「此人可就見，不可屈致也。將軍宜枉駕顧之。」
Whether crouching dragon was a well-known alias of Zhuge's, or (as the novel asserts) says that Zhuge was a peerless intellect, or simply used as an exaggeration by Sima and Xu is up to interpretation. It's also unclear how Xu Shu managed to convince Liu; maybe he was very persuasive, or trusted. We also don't know why Liu must visit personally, and not simply summon Zhuge; maybe Xu Shu said something like "you have to go and see for yourself".
He was handsome and tall. In those days looking good was considered a virtue in and of itself. Even Records bothers to mention that he is 8 chi tall (basically 6 foot) 身長八尺. There's an interesting anecdote of Cao Cao disguising one of his more handsome officials as himself, and himself as a guard, when meeting a Hun envoy because he was ashamed of being short and ugly.
Finally, consider Liu's position: although famous, he was extremely weak and desperate. At this point he had been taking refuge under Liu Biao for years, with barely a few thousand troops under his command.
曰：「今皆不及，而將軍之眾不過數千人，以此待敵，得無非計乎！」
His position is precarious; he has no land of his own, administering the tiny town of Xinye, sandwiched between a powerful enemy (Cao Cao) and his lord Liu Biao, unable to expand and unable to strengthen lest he becomes a threat to Liu Biao. He desperately needs wise men to form and execute a plan, without which he says "what can I do?"
備曰：「我亦愁之，當若之何？」
Under such circumstances, it may have been easy for people like Xu Shu to convince him to meet with Zhuge personally.
