As other people mentioned, putting -ss before (much faster) or after (more accurate) the -i makes a big difference. The section "Fast And Accurate Seeking" on the ffmpeg seek page tells you how to get both, and I have used it, and it makes a big difference. Basically you put -ss before AND after the -i, just make sure to leave enough time before where you want to start cutting to have another key frame. Example:
If you want to make a 1-minute clip, from 9min0sec to 10min 0sec in Video.mp4, you could do it both quickly and accurately using:
ffmpeg -ss 00:08:00 -i Video.mp4 -ss 00:01:00 -t 00:01:00 -c copy VideoClip.mp4
The first -ss seeks fast to (approximately) 8min0sec, and then the second -ss seeks accurately to 9min0sec, and the -t 00:01:00 takes out a 1min0sec clip.
Also note this important point from that page: "If you use -ss with -c:v copy, the resulting bitstream might end up being choppy, not playable, or out of sync with the audio stream, since ffmpeg is forced to only use/split on i-frames."
This means you need to re-encode the video, even if you want to just copy it, or risk it being choppy and out of sync. You could try just -c copy first, but if the video sucks you'll need to re-do it.