Valencia is the birthplace of paella, and you should eat it here at least once. The original Valencian paella has chicken, rabbit, and sometimes snails — never seafood. For seafood paella (paella de marisco) head to the beach restaurants in El Cabanyal. Both versions are traditionally a midday dish — most restaurants only make rice at lunch.
Beyond rice, the city's other specialities are worth seeking out: fideuà (a paella made with short noodles instead of rice, usually with seafood and a side of allioli), arròs negre (rice cooked black with squid ink), and esgarraet (roasted red peppers and salt cod with garlic and olive oil). For dessert, finish with horchata — a cold drink made from tiger nuts — and a sweet, crunchy fartón pastry to dunk in it. The best horchata comes from the village of Alboraia just north of the city, but the venerable Horchatería Santa Catalina in the old town will do nicely.
Spanish mealtimes apply: lunch from around 1:30 to 4 pm, dinner from 9 pm onwards. Showing up at 7 pm will get you nothing but funny looks.