A Frame is usually used as a geometry master for other widgets.
Since an application usually has numerous widgets, you'll often want to contain them all in a Frame, or at least use the Frame to add some borderwidth, padding, or other nicety.
Many example snippets you might find on the web do not use a Frame because
they just want to demonstrate some feature in the shortest amount of code.
So, use a Frame if you need it, otherwise, do not.
Edit: I think the best way to organize a GUI is given in this Tkinter tutorial:
simpleApp.py:
import Tkinter as tk
class SimpleApp(object):
    def __init__(self, master, **kwargs):
        title=kwargs.pop('title')
        frame=tk.Frame(master, **kwargs)
        frame.pack()
        self.label = tk.Label(frame, text=title)
        self.label.pack(padx=10,pady=10)
if __name__=='__main__':
    root = tk.Tk()
    app = SimpleApp(root,title='Hello, world')
    root.mainloop()
This is mainly like your first example in that SimpleApp inherits from object, not Frame. I think this is better than subclassing Frame since we are not overriding any Frame methods. I prefer to think of SimpleApp as having a Frame rather than being a Frame.
Having SimpleApp subclass object does have a significant advantage over subclassing tk.Tk, however: it makes it easy to embed SimpleApp in a larger app:
import simpleApp
import Tkinter as tk
class BigApp(object):
    def __init__(self, master, **kwargs):
        title=kwargs.pop('title')
        frame=tk.Frame(master, **kwargs)
        frame.pack()
        self.simple = simpleApp.SimpleApp(frame,title=title)
        frame.pack(padx=10, pady=10)
        self.simple2 = simpleApp.SimpleApp(frame,title=title)    
        frame.pack()
if __name__=='__main__':
    root = tk.Tk()
    app = BigApp(root,title='Hello, world')
    root.mainloop()
Thus, simpleApp.py can be a stand-alone script as well as an importable module.
If you try this with SimpleApp inheriting from tk.Tk, you end up with extra undesired windows.