MySQL query very slow on Amazon RDS but really fast on my laptop?

Try experimenting with the Provision IOPS that RDS offers. Regardless of instance size, the IO is limited, and you can use the Provision IOPS settings, at an additional cost, to improve IO performance.

You can provision up to 3TB storage and 30,000 IOPS per database instance. For a workload with 50% writes and 50% reads running on an m2.4xlarge instance, you can realize up to 25,000 IOPS for Oracle and 12,500 IOPS for MySQL. However, by provisioning up to 30,000 IOPS, you may be able to achieve lower latency and higher throughput. Your actual realized IOPS may vary from the amount you provisioned based on your database workload, instance type, and database engine choice. Refer to the Factors That Affect Realized IOPS section of the Amazon RDS User Guide to learn more.

You can convert from standard storage to Provisioned IOPS storage and get consistent throughput and low I/O latencies. You will encounter a short availability impact when doing so. You can independently scale IOPS (in increments of 1000) and storage on-the-fly with zero downtime. The ratio of IOPS provisioned to the storage requested (in GB) should be between 3 and 10. For example, for a database instance with 1000 GB of storage, you can provision from 3,000 to 10,000 IOPS. You can scale the IOPS up or down depending on factors such as seasonal variability of traffic to your applications.

AWS RDS Provision IOPS