The best services to use when moving to Nepal

Priscilla, that is a tall order, but let me try and answer.
First, I note that all your questions about Services relate directly to the past, namely "on arrival"
And as I arrived in Nepal more than twenty years ago, it is obvious and to be expected that the services which existed then are vastly different from what they are today  - or say in the last 5 years. One thing is sure, prices have moved up like nobody's business over that very long time span. Some services (see below) - like Notarial Services did not exist when I first set foot on Nepalese soil. Let's be precise: Notarial Public Services were not introduced in Nepal until 2007 - ten years ago - Today, this type of service offers Attestation of Official Documents, Certification of Documents, and some but NOT all offer translation services. Notarial Offices can be found pretty much throughout the country. In Kathmandu today, for example, you can find a Notary Public in some small one man office. I know of at least one in Thamel, in the city. On the other hand, say you go and see your lawyer where so many have offices in Amannagar, your lawyer there may tell you he serves a dual function of acting as both lawyer and Notary too. Fees vary widely.
Interesting what Mulder said, as I had an identical experience when I arrived in Kathmandu. The Manager of the then so-called" Pilgrims Hotel" (since then, change of name and management) was really most helpful to me and he made me feel welcome and "at home". He was most jovial and we could joke and chat, have a beer together etc. Let's face it, Kathmanduites in particular have changed a huge amount since then. There was a "naivete" about the nepalese people  as the French say about them at that time, which I regret to say has waned a huge amount since then. I am not the only one to think along those line. It caused on Nepalese friend to remark to me one day not so long ago:  "The Nepalese people have lost their innocence over the last decade" 
Mulder speaks about massages. Of course he is dead in his comments about "massages being overpriced" and all the scams, which are in similar vein to those abuses I deplored in writing on my  about "pure baby yak wool" found in stores everywhere when in fact they are pure acrylic and nothing else. In terms of Priscilla's guidelines, ...and brands .....let's face it:  brands in Nepal are not protected - and no way/legislation, so it seems - to protect a brand (or copyright).  Take North Face - they do have one store in the center of town, with genuine North Face but for that one outlet,
there are 100 other stores which sell pure copies. (note; As I recall the head of North Face in Nepal readily admitted his genuine NF goods all came from Bangladesh, where they were made in factories there.)  This having been said, the item you pay $120 at the genuine NF, you can buy in other places copycat "made in Nepal" style for $15 to $25!  But for those copies, look for and inspect the sewing -
straight or zigzag? -  the C or D quality of the zipper which can break after only day (and not the high quality long lasting PKK brand) .....not to mention the poor quality dies they use in copies, using the cheapest ones from India! Put those items in the washing machine...see what happens!!
Returning to massages for a sec, the massage parlors of Kathmandu do not have a good reputation either. Obviously, if you go to a big luxury hotel, you can get a good massage there by a well trained massage therapist and there may be a few that are "ok". But the majority of them ....I would stay away from, honestly. These are questionable establishments, often dirty and operated by men/women with little or no  training - and little or no principles. From time to time, the Police raids them for irregularities or worse, close them down in case of efractions to the law.
I return to the strict guidelines:
INTERNET CAFE SERVICES - Twenty years ago, they were fantastic and they were everywhere. At that time, internet was taking off, and they had every facility under the sun,  including FAX machines. specially in Kathmandu. I remember one in particular called VisitNepal. Run by great and friendly people, they were a joy to work with. One day -maybe 10-12 years ago - the head of VisitNepal near the Vaishili closed his three floors of internet and other services, with large number of staff, and left for America. For me, it was the clear indication that internet services were on their wane. Today, there are a few left, maybe 4-6 in the very center of Thamel , almost impossible to send a fax out from Thamel, because the main cable is always in state of repair. So one has to go just beyond Durbar Marg to send a fax.  Besides, who sends faxes today?  (limited demand or use)
POSTAL SERVICES AND MAIL - Being a slow learner, it took me five years following my arrival in Nepal just to figure out that I lived at No. 100 Thamel Margh !! Besides, not everyone can read street signs and numbers... if present. Besides there are no postmen in Kathmandu anyway! Now the good part. I cannot speak about other cities, but in Kathmandu, you do not have to go to the Main Government Post Office to send a registered letter, say. For only about 1000/1200 rupees a year, one can rent out a box in a privately owned local post office which is near Java Cafe, Himalayan Bank etc.  They are very efficient and extremely polite and helpful. You have your own box and key to the box. However if you have an item shipped in from your country, 9 times out of 10, it will end arrive by notification to go and collect it from the big Central Government post office in Sundhara. It's called GPO. When you go to collect your package, be prepared to spend one hour minimum.  You will have to stand in line, fill out  2-4 forms, pay a possible tax (amount can vary widely from 50 to 1000 rupees, depending on content etc.) and stand by while an inspector watches you open the package, to ensure it is "safe" and not a prohibited product, drug etc.  I invite other subscribers to give information about postal services, outside of Kathmandu.
BANKING SERVICES
When I arrived way back, the commercial banks were many less in number. In the last 10-15 years, there have been many mergers and almost all of them have opened numerous not to say hundreds of branches everywhere. When I arrived ATM's were few and far between. Today, they are all over. So banking services from the larger and better known and most reputable banks are generally good. In the last 2-3 years, all the banks are more closely scrutinized than ever before by the Central Bank (Nepal Rastra Bank - NRB) and it is not uncommon to go into Chartered, or NIBL or Lumbini or some other bank and see NRB inspectors there and everywhere inspecting books and accounts. In the last year or so, supervision  of banking system by NRB has been more stringent than ever.
MONEY TRANSFER SERVICES
Mulder's remark is correct. My take on this is that Western Union can receive foreign monies from abroad and pay out in Nrs local currency in Nepal, but cannot and is not authorized to transfer any funds out or back to your country. My experience is that Western Union is not cheap. For example, if the bank rate for the euro is 115 Nrs, at the bank, they should exchange and give you more or less that rate. So if you exchange 100 dollars at the bank, you get say 11,500 rupees. But watch what Western Union does! They may well give you a rate of 5-7 rupees lower ..... depending on which agency you go to...to exchange...with the result is that they may only hand you 11,000  nrs or if they use a lower rate, they will convert at 108 which means that you only get 10,800 nrs
I always found that Moneygram gave a better rate, and if you can do it, ask the send or remitter of that money to send it NET of Commission, if you can manage it.  There are several other money remitters but believe these two are the main ones.
AUTHORIZED MONEY CHANGERS IN THE CITY AND ELSEWHERE
To get the going or current exchange daily rate, simply go to Google and enter, say, Nepal Investment bank Exchange rate.  Right away the daily prevailing rate is posted there on your internet screen. But if you compare that rate with what the currency booth dealers/authorized Exchange Dealers in Central Kathmandu are quoting that same day on the street booths, the rate offered by them will generally be plus or minus 2 rupees less/lower than what you will get if you take the trouble to walk into a commercial bank and do your exchange dealing there.
DRY CLEANING OF CLOTHES
On a totally different register, if you are living in or near the capital, I got excellent dry cleaning and other wash services always, over all those years, at one of the five or six large Bhatbhateni stores.
Surely there are other places, but my personal experience with them was flawless over a ten to fifteen year period.
TOURISM/VISIT TO PASHUPATINATH - LISTED AS WORLD HERITAGE SITE BY UNESCO
This site not so far from Kathmandu is well worth a visit, as it is a famous and sacred Hindu Temple dedicated to Pashupati on the banks of the Bagmati river.  It is reputed to be the oldest Hindu temple in Kathmandu, and it is filled with burning ghats and saddhus. Again ten to fifteen years ago, I remember going there but nowadays when I take a  group of visitors there, and because the people I take are all foreigners, they are asked to pay a staggering 1000 Nrs entrance fee, which is a lot of money by any standard. For the standard trekker or backpacker it is a good part of his daily expense budget. Besides, the inside of the Temple is off limits to foreigners as they are to all non-hindus. This has for result that they have to see it usually from the other side of the river - at a distance. By way of comparison, the last time I checked, the entrance fee for the same visit from anyone from the SAARC region was 50 Nrs. For nepalese visitors, the visit is free.
As the site is some distance from the center of Kathmandu, most visitors take a taxi which with waiting time may come to about 15 dollars. A guide is available and maybe you can bargain with him, but that cost may add up to say plus or minus another 10 dollars.
OTHER SERVICES
I can think of many other services that could be reviewed here. Perhaps other contributors can make their further contribution to these columns and cover, notably, LEGAL SERVICES, HEALTH SERVICES, TRANSPORTATION SERVICES, AND MUCH MORE.