TL;DR
The rules have not changed (more about that below) and based upon your friend's narrative it was a fair cop. She was outside of the rules, no question about it, but this could have been handled with a better outcome and she could have been admitted. Based on her narrative they gave her about 4 chances to turn things around and apparently they all but bent over backwards (they were a whole lot more civilised than the other removals in our archives). She did not avail herself of those opportunities and instead dug herself in deeper. Now matters are worse.
Full Answer
Your friend was refused leave to enter under Part 9 of the Immigration Rules; all removals from port use Part 9 of the rules (or its restatement in Appendix V of the rules). The removal notice does not cite the specific paragraph/subparagraph but it will most likely be Paragraph 320 (1)...
(1) the fact that entry is being sought for a purpose not covered by
these Rules;
The visitor rules
Your friend sought entry as a non-visa national who was making a short visit to the UK and so Appendix V of the Rules was engaged. These rules were drafted in the spring/summer of 2014 in a closely knit back-and-forth consultation between the Home Office and various members of the UK legal community. All told it took about 4 months and nobody on either side of the fence wants to do it again because it is too much agony. The rules were enacted in the Immigration Act 2014 and activated in April 2015. They have not changed since that time.
The landing interview
Specifically, your friend sought entry to speak at a conference (fee or honorarium or expenses-paid or whatever is all irrelevant). This is an activity that is not recreational and so "Visitors Appendix 3: Permitted Activities" comes in to play. What she proposed to do isn't found in the list of permitted activities and that's where she hit a rough spot...
Detention
She was placed in one of the mixed gender detention rooms and they gave her another interview (or more precisely, another opportunity to turn things around). That was her chance to get a temporary admission for a period of usually 2 - 7 days. This didn't happen.
Through what I count to be three separate interviews one of which was with a Chief IO. While a CIO must approve each removal, it's rare for them to engage the person directly. Something went terribly, terribly wrong and they were upset. It's easy to put all of this on the Border Force as demonic creatures given to sadism, but that proposition becomes awkward against the fact that they land 10+ million visitors a year without incident.
The removal
She was served an IS82, which is the form they use when someone does not qualify for leave-to-enter AND their behaviour is inappropriate. It gives them the option, but not the obligation, to have her placed on the Home Secretary's exclusion list (that's a bad thing). They removed her to NYC instead of her base on the USA's west coast. They didn't have to do that, there are flights out to the west coast all the time, but that was just icing on the cake. Minimal compliance.
Going forward
She has a removal which is computer linked to her biometrics, but worse is what's in her transcript. It cannot be expunged, but it can be relatively 'cleared' or mitigated by obtaining an entry clearance. It costs GBP 87 to apply for one, but I would emphatically recommend instructing a member of the UK Law Society with a practice area in prior removals who can word-smith an eloquent explanation.
Your questions...
If you hold a passport from one of the countries that normally
entitles you to request "leave to enter" on arrival in the UK, and
you're coming over to give a talk at a conference, what are the rules
on if you need to get a visa in advance?
If what you propose to do appears in the 'Permitted Activities' section of Appendix V, you can get leave-to-enter at the border. If you qualify for the 'Permitted Paid Engagements' rule (also in the same place), you can get leave-to-enter at the border. You will need to engage with the IO in a landing interview to be sure you qualify, so bring your stuff.
And does it vary depending on if the conference organisers are paying
for your flights/hotels or not? Or if they're giving you a small fee
or not?
Not really. It's very common for such people to have their expenses paid. In theory you are not supposed to collect a fee; I don't think they pay a lot of attention to honorariums and the like (unless you do something to get them upset).
Or if the conference organisers are a UK or EU registered company?
No. The organisers need to be UK-based. Minimally that means there's somebody here who is operating under a 'management scheme' (in whatever definition you can provide that can be called a 'management scheme'). Again, personal impact and articulation skills. It's just that simple.
Note: it's my own estimate that roughly 1 out of every 2,600 non-visa nationals arriving from North America will be refused entry at a port. People have said here on this site that this figure is too remote to worry about. Read it here. I think comparison with lightning is a flawed argument. When a removal happens it's a big time disruption, so it's best practices to be prepared for your landing interview.
Note: the Chief inspects the detention facilities at LHR and etc to assure they are up to scratch. They are not comparable to the diplomatic lounge in IAD, but they are not the hell-hole of Calcutta either. The Chief’s latest inspection report as per their web-page was published 16th July 2015.