How to send e-mail on user account update, but not on password reset?
1st rule

About your 1st rule, for which you wrote in your question this:


  Neither of the below rules work as expected, the first one only fires if both fields are changed


Sorry to say, but the Rules module is working as designed ... because within your Rules Conditions, you basically specified that BOTH conditions must be satisfied.

Actually you did not specify an AND or an OR, and therefor the 2 Rules Conditions are combined with the default operator ... which is AND.

2nd rule

About your 2nd rule, for which you wrote in your question this:


  The rule with an OR condition, this just never fires no matter what fields I change.


Sorry to say (again), but the Rules module is working as designed ... because within your Rules Conditions, you basically specified that 3 conditions must ALL be satisfied, i.e.:


Field "first name" must be changed, AND
Some "empty" OR construction must be TRUE (as is shown with the line in your exported rule that looks like { "OR" : [  ] }, ... there is nothing between the [  ] in it), AND
Field "last name" must be changed.


Your crucial error is within that 2nd condition: you started to add on "OR" construction, but you didn't specify the 2 conditions for which that "OR" should be used. You probably thought that Rules Condition 1 and 3 are the 2 conditions to be combined with that "OR", but that is not how the Rules syntax is like (confusing, I know, many users struggle with this ...).

Therefor, try this variation of your rule (and don't forget to complete the Rules Action to actually send that eMail):

{ "rules_account_update_2" : {
    "LABEL" : "Account Update 2",
    "PLUGIN" : "reaction rule",
    "REQUIRES" : [ "rules" ],
    "ON" : [ "user_presave" ],
    "IF" : [
      { "OR" : [ 
          { "NOT data_is" : {
              "data" : [ "account-unchanged:field-first-name" ],
              "value" : "[account:field-first-name]"
            }
          },
          { "NOT data_is" : {
              "data" : [ "account-unchanged:field-last-name" ],
              "value" : [ "account:field-last-name" ]
            }
          }
        ]
      }
    ],
    "DO" : [
      { "mail" : {
          "to" : "",
          "subject" : "",
          "message" : "",
          "from" : "",
          "language" : [ "" ]
        }
      }
    ]
  }
}


Note the difference here: this rule has 1 Rules Condition, which is an "OR"-construct, and 2 (sub) Conditions to be combined with that "OR" are your 2 Rules Conditions about first name and last name.

BTW, when debugging / developing Rules with a Rules Action to send an eMail, I always (temporary) replace such Rules Action with just a "display a message" (like "It works! Just rework the display of this message now to sending an eMail").

PS: I'm assuming this question is about D7.