Your assumptions are flawed.

When host 2 receives the ARP request from host 1, in addition to sending the ARP reply it should also update/add the entry for host 1 in it's own ARP table.

So your order should be extended to look more like this:

ARP-request host 1 to host 2
Host 2 updates or adds entry for host 1 in ARP table
ARP-reply host 2 to host 1
Host 1 adds entry for host 2 in ARP table
ICMP echo request host 1 to host 2
ICMP echo reply host 2 to host 1

As to why host 2 sends out an ARP request so soon after, I would guess that the OS you are using either keeps a short timer for entries added this way and sends an ARP request to minimize the impact of any potential ARP poisoning attacks. However this is only a guess and it would take looking into what the OS is actually doing to make sure.

For more detail on the ARP process, you can check out RFC 826. Here is the processing flow from the RFC:

Packet Reception:
-----------------

When an address resolution packet is received, the receiving
Ethernet module gives the packet to the Address Resolution module
which goes through an algorithm similar to the following.
Negative conditionals indicate an end of processing and a
discarding of the packet.

?Do I have the hardware type in ar$hrd?
Yes: (almost definitely)
  [optionally check the hardware length ar$hln]
  ?Do I speak the protocol in ar$pro?
  Yes:
    [optionally check the protocol length ar$pln]
    Merge_flag := false
    If the pair <protocol type, sender protocol address> is
        already in my translation table, update the sender
        hardware address field of the entry with the new
        information in the packet and set Merge_flag to true.
    ?Am I the target protocol address?
    Yes:
      If Merge_flag is false, add the triplet <protocol type,
          sender protocol address, sender hardware address> to
          the translation table.
      ?Is the opcode ares_op$REQUEST?  (NOW look at the opcode!!)
      Yes:
        Swap hardware and protocol fields, putting the local
            hardware and protocol addresses in the sender fields.
        Set the ar$op field to ares_op$REPLY
        Send the packet to the (new) target hardware address on
            the same hardware on which the request was received.