you might want to consider d3000, 450d, 1000d.
they all good for travelling. light and small

Nex 3~

Quite light, semi-DSLR. Should be enough 4 your usage.

check on d3000, I don't think you will say that heavy, unless you are using BAZOKA lens.

Erm around 1.4k or maybe more. Garage sales is the way to go

And as a sidenote, D3000 has no AF motor inside. Means if you intend 2 upgrade lens later in future, you need to buy lens with AF built in. Not worth spending that much for it. 

You can consider Nex3, if not, G12 makes a good option. Played with that b3fore.

dude.. ur case is just the same as mine. I got confused in the middle of of those 3 model (yesterday) Got my post summore here in this topic.
In the end I picked Nex 3 as my choice.The solution is: Its depend on how u view the design of the camera and ur usage. Google and youtube is ur good friend rite now. I watched review by this guy from digitalrev and quite convincing

S95 review:
http://www.youtube.com/watch?v=jVASN_QtCn0
Reason of not choosing:
It's 'TOO COMPACT' for me. I am a big guy, so if I bring this camera around would not suitable with my size. Its too small and I think it suitable for gurl use or as present for ur girlfriend rather than a guy usage.

G12 review:
http://www.youtube.com/watch?v=jto9C5uZIWU&feature=channel
Reason of not choosing:
I like the ergonomic design of G12. I would rather pick this 1 at first    . But its got too many dial which I might got confused later on as I'm just a noob in camera things 

Nex 3 review (Its a review of Nex 5 but.. hey both nex 3/5 is about the same):
http://www.youtube.com/watch?v=hBox_wfAM08
Reason of bought it:
I'm going to use the camera for food photo shooting. And Many review said that Nex 3 is very excellent performance in low light condition even without the flash. <-- (tested by me and suprisingly ITS TRUE)
And I like the panorama view very much   

So the decision is urs. Hope with this help ya searching for the best camera suit u. 

Yeap! both s95 and g12 lens are fixed. Nex series got the advantages of interchangeable lens. So, u will got the feeling of DSLR with the size of compact camera.
I took the 16mm. Somebody told me that 1855 is rather so-so. If u truely considering abt zooming better u buy the 18-200. but at the moment, the 16 lense is already enough for me. summore it kept the camera in 'compact look'. 

It's quite decent, really lol.
Erm, try Creative Damansara? The price there quite low. Go search garage sales also. Maybe got promotion.