theres a good one between seminyak/legian walking distance from jalan seminyak/legian on the side of the road just at the corner. ive heard there is a good one in kuta but u can find one in almost every town in the South.
the one i goto right now is by moped & the long street is called jalan toku marbara(not correct spelling, only how i heard it said). i get my durian there & also duku,mangii,rambutan etc. good fruits from villagers coming outside the city in their trucks to sell. its very near kerobokan prison, thats how i found it.
if u looking for a vegan/raw restaurant the best choices are obviously ubud but the one i goto is on jalan dhyana pura, its easy to get to from both seminyak & legian, its called zula restaurant.
ask them for "pasar beli buah", that means market to buy fruit. most of the locals will know on the street but some of them who dont will tell u to goto denpassar or kuta which u dont need as there is lots here.
i cant remember what corner exactly it was on but there was definitely a good one with loads of fruit stalls. i went to the carreffour supermarket on sunset road my first day here & had quite a good selection of fruits, lots of them are supermarket quality though, only the mangii i bought were great quality because theyre in season now, the rest werent.