Frame Relay is a WAN protocol that was originally developed for use with ISDN but can be used with other media. An FR circuit differs from a leased line in two major ways: first, it depends on shared bandwidth for some portion of the distance between A and B and second (and because it IS shared), all the data traffic has to share the same protocol.
That shared bandwidth is called the FR "cloud" because the packets go into the shared portion from one side and come out of the shared portion onthe other side, but what happens in between is not visible to you as a user.
The reason people say that FR works on leased lines is that you have to have a leased line of some sort to get from your premises to the FR switch at the C.O. A leased line can carry any form of digital or analog data for which it is provisioned so that could include data packaged for FR.
Cisco routers, for example, provide a choice between FR (between any two devices) or a proprietary encapsulation (Cisco) when both ends are Cisco.
The FR service can be provided to you by any carrier but depending on the state of de-regulation in your particular area, the local loop to your premises may have to be provided by your local telco (ILEC). The switches could be anywhere but are often co-located within a telco CO even if the vendor is not the telco.
As far as ISDN, the usual BRI ISDN allows for 128k of bandwidth on an instant dialup basis. A 128k Frame Relay would provide better performance because the circuit is always up so you don't have the momentary delay in bringing up the ISDN circuit. Often ISDN circuits are measured rate, which means they can get very expensive very fast. FR is usually flat-rate although there are all sorts of pricing structures possible.
paul