Why Manitoba or Nova Scotia? From what you say, you have no family in Canada. I do not think you should restrict yourself to a province yet.
Look for job offers online, say starting at http://www.jobbank.gc.ca/intro-eng.aspx
If you end up getting a job offer as a front desk clerk or similar, it would be best for you to be in Alberta or in BC. Front desk clerk is not a skilled job so it limits your options to immigrate but the provincial nominee programs in these provinces allow employers to sponsor front desk clerks and a handful of other occupations for PR due to shortage in the hotel industry.
You can find links to the PNP's here:http://www.albertacanada.com/immigration/immigrating/ainp-eds-semi-skilled-criteria.aspx#hotel
This is also a possibility in Nova Scotia under community identified stream but the unemployment in Nova Scotia is a lot higher than in AB for example so I think it would be harder for you to get an LMO there.
It may also be possible to do this in Manitoba but they have a points system, see http://www.immigratemanitoba.com/asset_library/2013/05/manitoba-immigration-mpnp-points-worksheet-interactive.pdf
I think BC or AB would be best because they have already identified this shortage of workers as well as they have much more tourism than MB and NS.
However, first you have to find that job and get that LMO and work permit. I would suggest that you stay away from agencies, especially if they want to charge you because there are a lot of scammers out there.