With a Lu Shang's from the start, 0-100 can take you 6-8 weeks if you fish every single day until fatigue. My general rule of thumb I noticed was every 200 fish got me about 1.5-2.5 skill levels. In more realistic terms, 0-100 took me about 10 months. Just find something that makes you a nice profit off of that has a decent level too. I only stayed in 4 different locations from my 0-100 journey. 0-30s was spent getting Lu Shang's in Windurst Woods, 30s-60s was in Qufim Island with Cone Calamary, Bluetail, and Gigant Squid, 60s-96 was in Talacca Cove on Dil, Mercanbaligi, and Ahtapots, and 96-100 was in Oldton Movopalos(sp?) on Armored Pisces. Good luck, and try not to drive yourself crazy over the slow skill ups as many of us have. =)
Watusa of Lakshmi
Same sorta thing with Watusa. I saw him fishing on the ferry one time. It felt like a hollywood celebrity sighting.