Generally speaking, most fossils in building stone are marine invertebrates of Paleozoic or Mesozoic age. Good building stone must be well-consolidated, which eliminates many terrestrial and marine formations of the Cenozoic, and generally leaves you with limestones, dolomites, and some kinds of sandstone if you're considering sedimentary rocks. Within these groups, fossils are often eliminated from dolomites by the process of dolomitization, and building-quality sandstone is often not as fossiliferous as limestone, although trace fossils may be present in both. This leaves us with limestones, which regular readers will know can be quite fossiliferous. The shallow marine conditions appropriate for good old fossiliferous limestone stopped being widespread on North America around the end of the Cretaceous, which is where the Paleozoic–Mesozoic qualification comes from. Finally, marine invertebrates are simply more common than any other kind of fossil that can be seen with the naked eye, which gives them an automatic leg or tentacle or foot or what-have-you up. (Note that you may see excellent fossils in building stone described as "marble", which is correct in the stone trade but inaccurate in geology. If it's got good fossils, it's not a geologic marble. Limestones that can be polished are included as marbles in the stone trade. Incidentally, this polish, which makes them so impressive in person, can make them difficult to photograph.)
|The path leading to Hidden Falls includes a retaining wall built of Platteville Formation pieces, many of which feature shells like the example adjacent to the coin, near the center of the photo.|
Sometimes, the fossils are quite obvious. Cross-sections through large mollusk shells, particularly snail and ammonite shells, are eye-catching, and the builders may have even arranged interesting fossils in visually prominent places. Although not as complex, sections through large bivalve shells are also visually interesting. Here are a couple of examples I encountered over 2014 in Washington, D.C.:
|Bivalve valve in the floor at the Jefferson Memorial, with appropriate coin for scale.|
|Two valves of a bivalve in the flooring stone on the second floor of the west building of the National Gallery of Art, near the men's room by the rotunda.|
Seemingly half of the stone in Washington is Salem Limestone, also known under the trade name of Indiana Limestone. It is Mississippian in age and is essentially made of teeny fossil fragments, big enough that you can see them if you get your nose right up to them, but small enough that the view probably won't edify you that much. If you're in Washington and you pass by a building made of a light gray stone that looks kind of like sandstone at sidewalk range, odds are it's this stuff. The Capitol Reflecting Pool is surrounded by Salem Limestone, and is one of the best places to see it. Aside from the favorable lighting, some of the stone used around the pool is coarser than the typical Salem Limestone used in the city and shows some relatively large fossils. Avoid the duck poop.
|Horn coral and various other things.|
|More bits, including an interesting fossil to the left of the dime. Coins just seem to follow me around.|
Speaking of which, bathrooms also feature a surprising amount of fossiliferous stone, although bathrooms being what they are, you are not encouraged to linger or take photographs. If you have a minute, spare a glance: circular fossils, like crinoid columnals and cross-sections through horn corals, are distinctive, as are comma- or eyelash-like sections through shells, similar to those above.
One drawback to building stone is that the provenance information is usually vague at best. A given building may have been constructed many decades ago, and the source of the stone is often known only to the trade name. Thus, the scientific value is limited, although the aesthetic value is still there. I've run into this with some interesting fossils in so-far unidentified interior building stone at the White House Visitor Center (the Malcolm Baldridge Great Hall in the Herbert C. Hoover Building, formerly the Patent Search Office) and at the Fredericksburg visitor center of Fredericksburg and Spotsylvania National Military Park.
It is not uncommon for a geologic survey or society to produce geologic walking tours for large cities. For example, considering Washington, the USGS has a tour, and there is a site dedicated to the city's "accidental museum" of paleontology. The city of St. Paul also has a guidebook (Kain, J., and P. Nelson. 2008. Rocky roots: geology and stone construction in downtown St. Paul. Ramsey County Historical Society, St. Paul [this is a revised edition of Kain's 1978 original volume]). Granted, you'll have to make do with some igneous and metamorphic rocks as well, but you'll probably get the hang of it. There is much of historic and cultural interest in building stones as well, which will show changes in wealth, trade, and architectural fashion.
[4:30 PM, 2015-01-04: edited the introduction because the last sentence of the paragraph did not properly follow]