They are really big videos, of several gigabytes, with 100-150mbps bitrate. These files load and play normally with any player. I don't think they are hard to decode, it's just that they have a very high bitrate. Taking them in After Effects, however, takes several minutes. It takes 2-5 minutes for a video to appear in the timeline, and then the preview takes again extra 2-5 minutes to load the first time. After these two long loads, the video plays smoothly in the AE preview panel and I don't have any problem. What is causing these long loads? Is there a way to improve them?
If performance is sluggish, I would make sure the videos are the same resolution and frame rate as the format you plan to deliver your final video in.
So if the videos you are trying to import are 4K, but you're working in HD in After Effects, I would transcode the videos down to HD.
Also use a non-GOP codec like ProRes instead of h264/mp4. They perform better when editing, because the software doesn't have to "look ahead" across multiple frames in order to work out how to draw the current frame.