I think this is regarded as the highest/longest cat in Britain
http://connect.garmin.com/activity/184675096. We are doing the Applecross one in September and that is about the same climb but you get the advantage of it being spread over a mile longer.
I'm also trying the Applecross one (Bealach Na Ba) in September. Looks a real beast, climbing 650 metres from sea level. It would definitely be a cat 1 climb if in the tdf.
I did a climb up the Col de l'Epine near Annecy last year that had recently featured as a cat 1 climb in that year's tour. That was only a 500 metre climb, over a distance of 7km, so had the normal level of height gain for a cat 1, but lengthwise it was on the shortish end of cat 1. Although I was chuffed to have got up it without stopping, If I'm honest, I think the category awarded to it was generous. I have a feeling that, because the big climbs had come earlier in the stage that went over that climb, the organisers put a few extra points on offer to keep the climbers interested and prevent the peloton from closing up. Had it been the first climb of the day, I'm sure it would have been a cat 2.
As to the OP's question as to where it all started, I believe the rating originally referred to the gear in which the tour director's car would have to be in to climb a hill. HC or "hors categorie" was awarded to a hill that the car could not get up at all. Cars have come on a long way since those days of course. The rating system might still apply to something like an Austin 7.