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.
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.
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.