Only incumbent presidents and vice-presidents, former presidents, and major presidential and vice-presidential candidates (and their families) get SS protection. Former VP’s get no SS protection, so the wishes of the Secret Service don’t enter into Gore’s travel arrangements.
Ex-presidents formerly got lifetime Secret service protection. This changed with a law enacted in 1997. Presidents elected before January 1, 1997, such as Jimmy Carter, George H. W. Bush, and Bill Clinton, can continue with lifetime SS protection. George W. Bush and later Presidents will only have protection for 10 years after leaving office. Former presidents may decline protection after leaving office if they so choose.
So, Al Gore can certainly choose to fly commercial flights.