The dolphins had deduced, correctly, that they would get second billing.
What does this sentence mean? Is "second billing" an idiom of some kind?
Dan Bron pointed out the essential answer more than a year ago in a comment beneath the poster's question:
Here, "billing" has its Broadway/Hollywood sense: how an actor or star's name appears in the beginning/ending credits of the work, on the marketing materials, promotional posters, theatre marquees, etc. "Second billing" means someone else is getting "top billing", or more attention/credit.
Don Wilmeth, The Language of American Popular Entertainment: A Glossary of Argot, Slang, and Terminology (1981) has this entry for billing:
Billing: 1. The ranking or mention of a performer's name in a show's ads or notices, which are displayed inside or outside a theatre or other place of entertainment, or distributed by hand. Top billing is a holdover from vaudeville in which the main attraction would be listed in the top of a bill of a program of number of acts, eight being the usual number. After top billing, an act, especially a new attraction, would prefer bottom billing, which was considered by many the first indication of success or recognition for virtual unknowns. [Cross reference omitted.] 2. Also the name for the notice or advertisement for a production or show.
So according to Wilmeth, in the old days of American vaudeville, "top billing" was best, "bottom billing" was second best, and "second billing" was nowhere to be found. In modern usage, however, "bottom billing" seems to have lost its sense of being a desirable spot on the bill, while "second billing" has emerged as a kind of consolation prize for the non-diva not-quite-headliner.
The intricacies of promotional billing in the modern (in 1964) film industry are the subject of Peter Bart, "Billing Without Cooing: Whose Name Goes Where in Screen Credits Is Still A Most Important Ploy for Hollywood Luminaries" (November 15, 1964) [combined snippets], reproduced in Gene Brown, The New York Times Encyclopedia of Film: 1964-1968 (1984):
Though this sort of compromise sometimes can be reached, many stars drive as hard a bargain as they can in each picture they make. In "Invitation to a Gunfighter" for example, Yul Brynner not only received the contractual right to have his name carried in all ads in the same type sue as the title of the film but also to decree the size of everyone else's name (Janice Rule was his co-star). In "Morituri," however, Brynner had to take second billing to Marlon Brando, a star who will never deign to occupy second place.
Elvis Presley, like Brando, flatly declines to take second billing and, in addition, refuses even to share the space over the titles in movie ads with any other performer. His name must stand alone above the name of the picture.
Many contracts for stars like Cary Grant or Rock Hudson stipulate not only the size of type but also its thickness, style and position. They also decree that the star's picture must always appear on the left side of the ad and that it must be larger than the picture of any other star. Agents for the fast-rising young , felt they had pulled off quite a coup recently by inducing Presley to make an exception and allow her name under his above "Viva Las Vegas."
Many supporting actors when denied top billing ask for special phraseology that will aid their status. In "The Loved One" Sir John Gielgud is listed as a "special guest star." In "Charade," Walter Matthau is listed as "co-star" but below the title and in notably smaller type than Cary Grant and Audrey Hepburn. In "I'd Rather Be Rich," Sandra Dee, Robert Goulet and Andy Williams are listed above the title while "Maurice Chevalier as Philip Dulaine" is listed in equal type below.
In the figurative sense in which Arthur Clarke uses second billing in 2010: Odyssey Two, the dolphins are not vying for the most prominent place on a placard announcing a theatrical production, but they do want paying attention to and they don't appreciate being a minor diversion:
Charming though they [the dolphins] were, he [Floyd] had to admit that their playfulness was sometimes a nuisance. ... But there had been one unforgettable occasion when the entire Board of Regents, in full evening attire, had been sipping cocktails around the pool while awaiting the arrival of a distinguished guest from the mainland. The dolphins had deduced, correctly, that they would get second billing. So the visitor was quite surprised to be greeted by a bedraggled reception committee in ill-fitting bathrobes—and the buffet had been very salty.